Arterial-based control of traffic flow in urban grid networks

Urban networks are typically composed of a grid of arterial streets. Optimal control of the traffic signals in the grid system is essential for the effective operation of the network. In this paper, we present mathematical programming models for the development of optimal arterial-based progression schemes. Such schemes are widely used for traffic signal control in arterial streets. Under such a scheme, a continuous green band is provided in each direction along the artery at the desired speed of travel to facilitate the movement of through traffic along the arterial. Traditional schemes consist of uniform-width progressions. New approaches generate variable bandwidth progressions in which each directional road section is allocated an individually weighted weighted that can be adapted to the prevailing traffic flows on that link. Mixed-integer linear programming is used for the optimization. Simulation results indicate that this method can produce considerable gains in performance when compared with traditional progression methods. By introducing efficient computational techniques, this method also lends itself to a natural extension for incorporation in a dynamic traffic management system.     

QoS-Guided Bandwidth Management in Differentiated Time Scales

This paper presents an integrated approach to QoS-guided network bandwidth allocation where each traffic flow requires a sufficient bandwidth allocation to support its mean traffic rate and to meet a delay requirement. Under the assumption that the peak rate of each traffic flow is decreasing with the time interval within which the rate is measured, we derive an analytical relationship between the delay bound and the bandwidth requirement for each individual flow. Then, based on a Gaussian aggregate traffic model, we show that two key controllable parameters, the coefficient of variation and the provision for variation for the aggregate traffic flow, determine all three fundamental QoS attributes (throughput, delay, and loss). We illustrate by examples that these results can be used to design admission policies. We demonstrate also quantitatively a remarkable QoS advantage of larger channel bandwidth in a statistical multiplexing environment. The analytical contributions are expected to be generally useful in QoS-guided bandwidth management in broadband networks.     

Call admission control schemes and ATM network topological design

Call admission control criteria are not only important for call admission control itself, but also can be an important input to network topological design. In this paper, we show the difference in terms of network cost incurred by adopting different call admission control schemes in network topological design. We compare two call admission control schemes. Scheme 1 uses equivalent bandwidth as its call admission control criterion and Scheme 2 is based on modeling the volatility of call traffic using Reflected Brownian Motion. Though Scheme 2 increases the complexity of network topological design, it can give lower network costs. Our experimental results show that for the same traffic mix, the network cost can be as little as 10% and as much as 35% lower when Scheme 2 is used instead of Scheme 1. The differences between the pair of resulting networks suggests that network topological design can be used as one of the criteria for choosing the call admission control scheme.     

Applications of SMP Bounds to Multi-class Traffic in High-speed Networks

In this paper, we consider the stochastic fluid-flow model of a single node in a high-speed telecommunication network handling multi-class traffic. The node has multiple buffers, one for each class of traffic. The contents of these buffers are multiplexed onto a single output channel using one of the service scheduling policies: the Timed Round Robin Policy or the Static Priority Service Policy. The Quality of Service requirements for each class are based on cell loss probabilities. Using effective bandwidth methodologies and the recently developed bounds for semi-Markov modulated traffic, we solve call admission control problems for the two service scheduling policies at this node. We compare the performance of the effective bandwidth methodologies and the SMP bounds technique. We also numerically compare the performance of the two service scheduling policies.     

Performance modeling of heterogeneous data networks

A heterogeneous data network consists of Local Area Networks (LANs) interconnected with either leased lines, packet-switched networks, Metropolitan Area Networks (MANs), or combinations thereof. Heterogeneous networks are characterized by bursty traffic, nested segmentation and reassembly of packets, window flow control and round-robin channel access. We develop a performance methodology for estimating user perceived delay and buffer overflow in heterogeneous data networks. The methodology is based on well-known two-moment approximation schemes. Modifications of these schemes are proposed in order to model the bandwidth allocation policies of the MANs and to capture the burstiness of the traffic. The methodology is applied to several LAN-MAN and LAN-MAN-WAN network examples.Supported partially through AT&T Grant No. 5-20491 and partially through NSF Grant No. NCR-8914447.     

Admission control of multi-class traffic with service priorities in high-speed networks

We consider a fluid model of a system that handles multiple classes of traffic. The delay and cell-loss requirements of the different classes of traffic are generally widely different and are achieved by assigning different buffers for different classes, and serving them in a strict priority order. We use results from the effective bandwidth of the output processes (see Chang and Thomas (1995)) to derive simple and asymptotically exact call-admission policies for such a system to guarantee the cell-loss requirements for the different classes assuming that each source produces a single class traffic. We compare the admission-control policies developed here with the approximate policy studied by Elwalid and Mitra (1995) for the case of two-class traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

The output of a switch,or, effective bandwidths for networks

Consider a switch which queues traffic from many independent input flows. We show that in the large deviations limiting regime in which the number of inputs increases and the service rate and buffer size are increased in proportion, the statistical characteristics of a flow are essentially unchanged by passage through the switch. This significantly simplifies the analysis of networks of switches. It means that each traffic flow in a network can be assigned an effective bandwidth, independent of the other flows, and the behaviour of any switch in the network depends only on the effective bandwidths of the flows using it. This revised version was published online in June 2006 with corrections to the Cover Date.     

A traffic shaping model for optimizing network operations

The management of technology in multi-service computer networks, such as university networks, has become a challenge with the explosive growth of entertainment oriented peer-to-peer (P2P) traffic. Traffic shaping is one of the tools used to manage bandwidth to improve system performance by allocating bandwidth between P2P and non-peer-to-peer (NP2P) traffic. We present a model for traffic shaping and bandwidth management that considers the trade-offs from allocating different amounts of bandwidths for different application categories and use data from a university network. The current policy allocates varying bandwidths over the day to P2P and NP2P traffic to reflect the importance of not letting entertainment based traffic choke the network during the day time at the expense of the more important traffic, such as Web traffic. We highlight the difficulties in obtaining data in the form required for analysis, and the need to estimate demand for allocations not covered by current policy. We present a goal programming model for this estimation task. We also model the traffic shaping problem as a Markov decision process and develop an algorithm for determining the optimal bandwidth allocation to maximize the utility of all users. Finally we use a numerical example to illustrate our approach.     

A hierarchical clustering scheme approach to assessment of IP-network traffic using detrended fluctuation analysis

This paper presents an approach to the assessment of IP-network traffic in terms of the time variation of self-similarity. To get a comprehensive view in analyzing the degree of long-range dependence (LRD) of IP-network traffic, we use a hierarchical clustering scheme, which provides a way to classify high-dimensional data with a tree-like structure. Also, in the LRD-based analysis, we employ detrended fluctuation analysis (DFA), which is applicable to the analysis of long-range power-law correlations or LRD in non-stationary time-series signals. Based on sequential measurements of IP-network traffic at two locations, this paper derives corresponding values for the LRD-related parameter α that reflects the degree of LRD of measured data. In performing the hierarchical clustering scheme, we use three parameters: the α value, average throughput, and the proportion of network traffic that exceeds 80% of network bandwidth for each measured data set. We visually confirm that the traffic data can be classified in accordance with the network traffic properties, resulting in that the combined depiction of the LRD and other factors can give us an effective assessment of network conditions at different times.     

一阶双曲型方程组初边值问题的差分格式及其稳定性

本文比较系统地讨论了有关数值求解两个自变量的一阶双曲型方程组初边值问题的某些问题,给出了几种能用于任何类型的初边值问题的差分格式,并在很宽的条件下证明了其中的某些变系数的初边值问题的差分格式对初值和边值是稳定的、差分格式所立出的方程组是良态的.其中的某些格式已用于解决某些复杂的实际问题(应用部分见[16]).     

Optimizing acyclic traffic signal switching sequences through an Extended Linear Complementarity Problem formulation

In this paper we first show how the Extended Linear Complementarity Problem, which is a mathematical programming problem, can be used to design optimal switching schemes for a class of switched systems with linear dynamics subject to saturation. More specifically, we consider the determination of the optimal switching time instants (the switching sequences are acyclic, but the phase sequence is pre-fixed). Although this method yields globally optimal switching time sequences, it is not feasible in practice due to its computational complexity. Therefore, we also discuss some approximations that lead to suboptimal switching time sequences that can be computed very efficiently and for which the value of the objective function is close to the global optimum. Finally we use these results to design optimal switching time sequences for a traffic signal controlled intersection so as to minimize criteria such as average queue length, worst case queue length, average waiting time, and so on.     

Multi-Product Expansion with Suzuki's Method:Generalization

In this paper we discuss the extension to exponential splitting methods with respect to time-dependent operators. We concentrate on the Suzuki's method, which incorporates ideas into the time-ordered exponential of [3, 11, 12, 34]. We formulate the methods with respect to higher order by using kernels for an extrapolation scheme. The advantages include more accurate and less computational intensive schemes for special time-dependent harmonic oscillator problems. The benefits of the higher order kernels are given on different numerical examples.     

Separable routing: A scheme for state-dependent routing of circuit switched telephone traffic

Separable routing is the first of a number of routing schemes for circuit switched telephone traffic invented at Bellcore. These routing schemes are state dependent, in the sense that, for each call attempt, a routing decision is made on the basis of the state of the network (defined in terms of the numbers of busy and idle trunks in the various trunk groups at the moment of the call attempt). In this paper, we describe separable routing and its mathematical background. Simulation results we have presented elsewhere show that the family of state-dependent routing schemes, of which separable routing is a member, is very attractive in terms of blocking rate, built-in network management features, and behavior in the presence of traffic forecast error.     

On second-order antidiffusive Lagrangian-remap schemes for multispecies kinematic flow models

This paper focuses on the numerical approximation of the solutions of multi-species kinematic flow models. These models are strongly coupled nonlinear first-order conservation laws with various applications like sedimentation of a polydisperse suspension in a viscous fluid, or traffic flow modeling. Since the eigenvalues and eigenvectors of the corresponding flux Jacobian matrix have no closed algebraic form, this is a challenging issue. A new class of simple schemes based on a Lagrangian- Eulerian decomposition (the so-called Lagrangian-remap (LR) schemes) was recently advanced in [4] for traffic flow models with nonnegative velocities, and extended to models of polydisperse sedimentation in [5]. These schemes are supported by a partial numerical analysis when one species is considered only, and turned out to be competitive in both accuracy and efficiency with several existing schemes. Since they are only first-order accurate, it is the purpose of this contribution to propose an extension to second-order accuracy using quite standard MUSCL and Runge-Kutta techniques. Numerical illustrations are proposed for both applications and involving eleven species (sedimentation) and nine species (traffic) respectively.     

A new high order compact off-step discretization for the system of 3D quasi-linear elliptic partial differential equations

We present a new fourth order compact finite difference scheme based on off-step discretization for the solution of the system of 3D quasi-linear elliptic partial differential equations subject to appropriate Dirichlet boundary conditions. We also develop new fourth order methods to obtain the numerical solution of first order normal derivatives of the solution. In all the cases, we use only 19-grid points of a single computational cell to compute the problem. The proposed methods are directly applicable to singular problems and the problems in polar coordinates, without any modification required unlike the previously developed high order schemes of [14] and [30]. We discuss the convergence analysis of the proposed method in details. Many physical problems are solved and comparative results are given to illustrate the usefulness of the proposed methods.     

Numerical algorithms for simulations of a traffic model on road networks

We introduce a simulation algorithm based on a fluid-dynamic model for traffic flows on road networks, which are considered as graphs composed by arcs that meet at some junctions. The approximation of scalar conservation laws along arcs is made by three velocities Kinetic schemes with suitable boundary conditions at junctions. Here we describe the algorithm and we give an example.     

Efficient public key encryption with smallest ciphertext expansion from factoring

For public key encryption schemes, adaptive chosen ciphertext security is a widely accepted security notion since it captures a wide range of attacks. SAEP and SAEP+ are asymmetric encryption schemes which were proven to achieve semantic security against adaptive chosen ciphertext attacks. However, the bandwidth for message is essentially worse, that is the ciphertext expansion (the length difference between the ciphertext and the plaintext) is too large. In most of the mobile networks and bandwidth constrained communication systems, it is necessary to securely send as many messages as possible. In this article, we propose two chosen-ciphertext secure asymmetric encryption schemes. The first scheme is a generic asymmetric encryption padding scheme based on trapdoor permutations. The second one is its application to the Rabin-Williams function which has a very fast encryption algorithm. These asymmetric encryption schemes both achieve the optimal bandwidth w.r.t. the ciphertext expansion, namely with the smallest ciphertext expansion. Further, tight security reductions are shown to prove the security of these encryption schemes.     

Adjoint IMEX-based schemes for control problems governed by hyperbolic conservation laws

Starting from relaxation schemes for hyperbolic conservation laws we derive continuous and discrete schemes for optimization problems subject to nonlinear, scalar hyperbolic conservation laws. We discuss properties of first- and second-order discrete schemes and show their relations to existing results. In particular, we introduce first and second-order relaxation and relaxed schemes for both adjoint and forward equations. We give numerical results including tracking type problems with non-smooth desired states.     

Optimal Base Station Positioning and Channel Assignment for 3G Mobile Networks by Integer Programming

In this paper, discrete mathematical programming approaches are used to solve the frequency allocation and cell site selection problem in an integrated setup. Both CDMA (code division multiple access) and FD/TDMA (frequency/time division multiple access) technologies will be important for 3rd generation mobile systems. If all users share the same bandwidth, base transmitter stations should be placed such that a maximum of traffic can be carried at low interference rates. The expected traffic is represented by spatially scattered weighted nodes. The problem to select an optimal set of base station locations from a given pool of configurations is formulated as an integer linear program and solved by combinatorial optimization methods. For systems which employ FD/TDMA schemes, the cell site optimization process depends on the assignment of channels. We suggest an integrated linear programming approach to solve both objectives in a single planning step. Because of the problems' tremendous complexity, special branch-and-bound procedures are developed as exact and approximate solution methods. An examples is given for a typical urban scenario with base transmitters below roof tops.     

M/D^{[y]}/1 Periodically gated vacation model and its application to IEEE 802.16 network

In this paper we consider the analysis of an \(M/D^{[y]}/1\) vacation queue with periodically gated discipline. The motivation of introducing the new periodically gated discipline lies in modeling a kind of contention-based bandwidth reservation mechanism applied in wireless networks. The analysis approach applied here consists of two steps and it is based on appropriately chosen characteristic epochs of the system. We provide approximate expressions for the probability-generating function of the number of customers at arbitrary epoch as well as for the Laplace–Stieljes transform and for the mean of the steady-state waiting time. Several numerical examples are also provided. In the second part of the paper we discuss how to apply the periodically gated vacation model to the non real-time uplink traffic in IEEE 802.16-based wireless broadband networks.