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.     

Multi-fractal analysis of IP-network traffic based on a hierarchical clustering approach

This paper describes an analysis of IP-network traffic in terms of the time variations in multi-fractal scaling properties. To obtain a comprehensive view in assessing IP-network traffic conditions, we used a hierarchical clustering scheme, which provides a way to classify high-dimensional data into a tree-like structure. Based on sequential measurements of IP-network traffic at two locations, we checked time variations in multi-fractal-related properties of measured data sets. In performing the hierarchical clustering-based analysis, we used four parameters: the highest value and the range of generalized fractal dimensions, the network throughput, and the standard deviation of average throughput for each measured data set. The results confirmed that the traffic data could be classified in accordance with the network traffic properties, demonstrating that the combined depiction of the multi-fractal-related properties and other factors can give us an effective assessment of network conditions at different times.     

Critical Thresholds for Dynamic Routing in Queueing Networks

This paper studies dynamic routing in a parallel server queueing network with a single Poisson arrival process and two servers with exponential processing times of different rates. Each customer must be routed at the time of arrival to one of the two queues in the network. We establish that this system operating under a threshold policy can be well approximated by a one-dimensional reflected Brownian motion when the arrival rate to the network is close to the processing capacity of the two servers. As the heavy traffic limit is approached, thresholds which grow at a logarithmic rate are critical in determining the behavior of the limiting system. We provide necessary and sufficient conditions on the growth rate of the threshold for (i) approximation of the network by a reflected Brownian motion (ii) positive recurrence of the limiting Brownian diffusion and (iii) asymptotic optimality of the threshold policy.     

MODWT-ARMA model for time series prediction

Many time series in the applied sciences display a time-varying second order structure and long-range dependence (LRD). In this paper, we present a hybrid MODWT-ARMA model by combining the maximal overlap discrete wavelet transform (MODWT) and the ARMA model to deal with the non-stationary and LRD time series. We prove theoretically that the details series obtained by MODWT are stationary and short-range dependent (SRD). Then we derive the general form of MODWT-ARMA model. In the experimental study, the daily rainfall and Mackey–Glass time series are used to assess the performance of the hybrid model. Finally, the normalized error comparison with DWT-ARMA, EMD-ARMA and ARIMA model indicates that this combined model is an effective way to improve forecasting accuracy.     

Optimization of Euclidean distance threshold in the application of recurrence quantification analysis to heart rate variability studies

An integrated approach is proposed to solve the optimization problem of the Euclidean distance threshold ε in recurrence quantification analysis (RQA), which is increasingly applied in the study of heart rate variability (HRV). In this paper, ε is inversely computed from a given recurrence rate (REC), the percentage of recurrence points. From the inversely computed ε, two other RQA output variables: determinism (DET), the percentage of recurrence points forming diagonal line structures, and laminarity (LAM), the percentage of recurrence points forming vertical and horizontal structures, are computed out as well. The trend of DET, LAM values at different REC levels (DLR trend) is introduced to comprehensively represent the dynamic properties of a time series. Based on the DLR trend, the variation of discrimination power, represented by the average loss (or Bayes risk), of DET and LAM, at different REC values is analyzed. Surrogate techniques are used to generate reliable test data sets for the discrimination evaluation. In particular, the results show that (1) the optimal REC can be much higher than the widely used 1% REC, and (2) after the optimization, the average loss can be reduced compared to 1% REC. It is also demonstrated that the optimal ε depends on the dynamic source and RQA variables, and the DLR trend based ε optimization method can improve RQA discrimination analysis especially for the short term HRV analysis.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

Formulation,Stability, and Computation of Traffic Network Equilibria as Projected Dynamical Systems

In this paper, we present a unified treatment and analysis of a dynamic traffic network model with elastic demands formulated and studied as a projected dynamical system. We propose a travel route choice adjustment process that satisfies the projected dynamical system. Under certain conditions, stability and asymptotical stability of the equilibrium patterns are then derived. Finally, two discrete-time algorithms, the Euler method and the Heun method, are proposed for the computation of the solutions, and convergence results established. The convergence results depend crucially on stability analysis. The performance of the algorithms is then illustrated on several transportation networks.     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Calculation of traffic flow breakdown probability to optimize link throughput

Traffic breakdown phenomenon is prevalent in empirical traffic system observations. Traffic flow breakdown is usually defined as an amount of sudden drop in traffic flow speed when traffic demand exceeds capacity. Modeling and calculating traffic flow breakdown probability remains an important issue when analyzing the stability and reliability of transportation system. The breakdown mechanism is still mysterious to practitioners and researchers in varying manner. Treating breakdown as a random event, this paper use discrete time Markov chain (DTMC) to model traffic state transition path, as a result, a transition probability matrix can be generated from empirical observations. From empirical analysis of breakdown, we found this formulation of breakdown probability follows the Zipf distribution. Therefore, a connection from traffic flow breakdown probability to how many vehicles are occupying a certain freeway segment (e.g. a link) will be established. Following from the results, a quantitative measure of breakdown probability can be obtained to optimize ramp metering rates to achieve optimum system performance measures.     

Asymptotic properties of LSE of regression coefficients on singular random fields observed on a sphere

We present some upper bounds on the rate of convergence in the central limit theorem for normalized least square estimates (LSE) in a spherical regression model with long range dependence (LRD) stationary errors. The used method is based on the asymptotic analysis of orthogonal expansion of non-linear functionals of homogeneous isotropic Gaussian random fields and on the Kolmogorov distance. The theory have many applications in science for instance in evaluating the COBE data.     

An improved seasonal rolling grey forecasting model using a cycle truncation accumulated generating operation for traffic flow

Accurate real-time prediction of urban traffic flows is one of the most important problems in traffic management and control optimization research. Short-term traffic flow has complex stochastic and nonlinear characteristics, and it shows a similar seasonality within intraday and weekly trends. Based on these properties, we propose an improved binding cycle truncation accumulated generating operation seasonal grey rolling forecasting model. In the new model, the traffic flow sequence of seasonal fluctuation is converted to a flat sequence using the cycle truncation accumulated generating operation. Then, grey modeling of the cycle truncation accumulated generating operation sequence weakens the stochastic disturbances and highlights the intrinsic grey exponential law after the sequence is accumulated. Finally, rolling forecasts of the limited data reflect the new information priority and timeliness of the grey prediction. Two numerical traffic flow examples from China and Canada, including four groups at different time intervals (1 h, 15 min, 10 min, and 5 min), are used to verify the performance of the new model under different traffic flow conditions. The prediction results show that the model has good adaptability and stability and can effectively predict the seasonal variations in traffic flow. In 15 or 10 min traffic flow forecasts, the proposed model shows better performance than the autoregressive moving average model, wavelet neural network model and seasonal discrete grey forecasting model.     

Multiscale Analysis and Data Networks

The empirical finding of self-similarity in data network traffic over many time scales motivates the need for analysis tools that are particularly well adapted for identifying structures in network traffic. These structures span a range of time scales or are scale-dependent. Wavelet-based scaling analysis methods are especially successful, both collecting summary statistics from scale to scale and probing the local structure of packet traces. They include both spectral density estimation to identify large time-scale features and multifractal estimation for small time-scale bursts. While these methods are primarily statistical in nature, we may also adapt them to visualize the “burstiness” or the instantaneous scaling features of network traffic. This expository paper discusses the theoretical and implementation issues of wavelet-based scaling analysis for network traffic. Because data network traffic research does not consist solely of analysis, we show how these wavelet-based methods may be used to monitor and infer network properties (in conjunction with on-line algorithms and careful network experimentation). More importantly, we address what types of networking questions we can and cannot investigate with such tools.     

Heavy-traffic analysis of the sojourn time in a three node Jackson network with overtaking

We consider a Jackson network consisting of three first-in-first-out (FIFO)M/M/1 queues. When customers leave the first queue they can be routed to either the second or third queue. Thus, a customer that traverses the network by going from the first to the second to the third queue, can be overtaken by another customer that is routed from the first queue directly to the third. We study the distribution of the sojourn time of a customer through the three node network, in the heavy traffic limit. A three term heavy traffic asymptotic approximation to the sojourn time density is derived. The leading term shows that the nodes decouple in the heavy traffic limit. The next two terms, however, do show the dependence of the sojourn times at the individual nodes and give quantitative measures of the effects of overtaking.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

A defect-correction method for unsteady conduction-convection problems II: Time discretization

In this paper, a fully discrete defect-correction mixed finite element method (MFEM) for solving the non-stationary conduction-convection problems in two dimension, which is leaded by combining the Back Euler time discretization with the two-step defect correction in space, is presented. In this method, we solve the nonlinear equations with an added artificial viscosity term on a finite element grid and correct these solutions on the same grid using a linearized defect-correction technique. The stability and the error analysis are derived. The theory analysis shows that our method is stable and has a good convergence property. Some numerical results are also given, which show that this method is highly efficient for the unsteady conduction-convection problems.     

A new multifractal network traffic model

In this paper, a new multifractal traffic model to capture the multifractal nature of modern Internet traffic was developed. Employing the algorithm of network traffic analysis (binomial inverse cascade process) to analyze the multifractal feature of traffic data and adopting the algorithm of network traffic synthesis (binomial cascade process) to model the network traffic, this approach gave an easy and efficient way to infer the model parameters from the measured traffic traces. Moreover, the traffic was simulated and analyzed using obtained parameters. It was found that the simulated traffic data were in a close fit to the real trace statistics. The analysis results showed that this model could capture the real network traffic very well.     

System optimal and user equilibrium time-dependent traffic assignment in congested networks

This paper formulates two dynamic network traffic assignment models in which O-D desires for the planning horizon are assumed known a priori: the system optimal (SO) and the user equilibrium (UE) time-dependent traffic assignment formulations. Solution algorithms developed and implemented for these models incorporate a traffic simulation model within an overall iterative search framework. Experiments conducted on a test network provide the basis for a comparative analysis of system performance under the SO and UE models.     

Analysis of a modified two-lane lattice model by considering the density difference effect

In this paper, a modified lattice hydrodynamic model of traffic flow is proposed by considering the density difference between leading and following lattice for two-lane system. The effect of density difference on the stability of traffic flow is examined through linear stability analysis and shown that the density difference term can significantly enlarge the stability region on the phase diagram. To describe the phase transition of traffic flow, the Burgers equation and mKdV equation near the critical point are derived through nonlinear analysis. To verify the theoretical findings, numerical simulation is conducted which confirms that traffic jam can be suppressed efficiently by considering the density difference effect in the modified lattice model for two-lane traffic.     

基于匝道调节和可变限速的快速路交通控制

论证了交通网络中所有车辆花的时间的极小值等价于网络的最大输出流.同时在考虑可变速度限制,入口匝道调节和瓶颈等几个因素的前提下,根据情况我们合理选择这三者间的组合,从而获得交通网络控制的最佳性能.通过定量分析法,我们给出了一个仿真例子,说明了此方法的实用性.目的是给交通控制中心的决策部门一个依据,何时采用三者间的协调,何时可以不需要.     

A GIS-based decision support system for planning urban transportation policies

A decision support system (DSS) integrated in a geographical information system (GIS) for the analysis and evaluation of different transport policies is presented. The objective of the tool is to assist transport administrators enhance the efficiency of the transportation supply while improving environmental and energy indicators. The DDS works on three levels. The first performs the transport network analysis, the second assesses the energy consumption and pollutant emissions and the third evaluates the several policies selected. Road traffic is simulated using a deterministic, multi-modal traffic assignment model with capacity constraints. The model allows the estimation of traffic flow patterns within each link of the road network starting from the knowledge of the network characteristics and traffic demand. Energy consumption and pollutant emission calculations are based on the methodology developed by the CORINAIR working group. The evaluation of each policy scenario is based on a number of traffic, environmental and energy indicators. A multi-criteria analysis, where decision is based upon judging over appropriate weighted criteria, is adopted. Models are integrated in a GIS environment, which serves as the repository of the data as well as the user interface of the tool. The use of the tool is demonstrated through characteristic case studies on the Greater Athens Area in Greece. Two policy measures, one concerning the extension of the region where half of the private cars are prohibited from entering to the Municipality of Athens and the other the reduction of parking places in the same region by 50% are evaluated.