A Traffic Engineering Approach for Placement and Selection of Network Services

Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We divide the problem into two subproblems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering.     

Multiply-rooted multiscale models for large-scale estimation

Divide-and-conquer or multiscale techniques have become popular for solving large statistical estimation problems. The methods rely on defining a state which conditionally decorrelates the large problem into multiple subproblems, each more straightforward than the original. However this step cannot be carried out for asymptotically large problems since the dimension of the state grows without bound, leading to problems of computational complexity and numerical stability. In this paper, we propose a new approach to hierarchical estimation in which the conditional decorrelation of arbitrarily large regions is avoided, and the problem is instead addressed piece-by-piece. The approach possesses promising attributes: it is not a local method-the estimate at every point is based on all measurements; it is numerically stable for problems of arbitrary size; and the approach retains the benefits of the multiscale framework on which it is based: a broad class of statistical models, a stochastic realization theory, an algorithm to calculate statistical likelihoods, and the ability to fuse local and nonlocal measurements.     

Estimating point-to-point and point-to-multipoint traffic matrices: an information-theoretic approach

Traffic matrices are required inputs for many IP network management tasks, such as capacity planning, traffic engineering, and network reliability analysis. However, it is difficult to measure these matrices directly in large operational IP networks, so there has been recent interest in inferring traffic matrices from link measurements and other more easily measured data. Typically, this inference problem is ill-posed, as it involves significantly more unknowns than data. Experience in many scientific and engineering fields has shown that it is essential to approach such ill-posed problems via "regularization". This paper presents a new approach to traffic matrix estimation using a regularization based on "entropy penalization". Our solution chooses the traffic matrix consistent with the measured data that is information-theoretically closest to a model in which source/destination pairs are stochastically independent. It applies to both point-to-point and point-to-multipoint traffic matrix estimation. We use fast algorithms based on modern convex optimization theory to solve for our traffic matrices. We evaluate our algorithm with real backbone traffic and routing data, and demonstrate that it is fast, accurate, robust, and flexible.     

Multicast-based inference of network-internal delay distributions

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.     

The Potential of End-to-End Observations in Trouble Localization and Quality Control of Network Links

Algorithms for the use of Origin-to-Destination (Endto-End) observations for the monitoring of direct network links (direct finals or primary high usage groups) were previously proposed and analyzed. In this paper a theoretical framework intended to shed insight on the potential for also monitoring non-direct network links is developed. In particular, a maximum likelihood based approach is applied to an idealized network model with fixed routing probability structure and point-to-point loads. This approach allows sufficient conditions for the identifiability (estimation) of a fixed set of per link call failure probabilities to be developed, indicating that identifiability problems can be resolved by the addition of observations on selected links from tandems. Because of the dynamically changing character of network loads and hence routing probabilities, the extension appears thus attractive to implement only for limited portions of the network. Through the proposed scheme, unnecessary complexity in the minicomputer network that realizes the quality control of the network links is avoided.     

Multi-hour, multi-traffic class network design for virtualpath-based dynamically reconfigurable wide-area ATM networks

The virtual path (VP) concept has been gaining attention in terms of effective deployment of asynchronous transfer mode (ATM) networks in recent years. In a recent paper, we outlined a framework and models for network design and management of dynamically reconfigurable ATM networks based on the virtual path concept from a network planning and management perspective. Our approach has been based on statistical multiplexing of traffic within a traffic class by using a virtual path for the class and deterministic multiplexing of different virtual paths, and on providing dynamic bandwidth and reconfigurability through virtual path concept depending on traffic load during the course of the day. In this paper, we discuss in detail, a multi-hour, multi-traffic class network (capacity) design model for providing specified quality-of-service in such dynamically reconfigurable networks. This is done based on the observation that statistical multiplexing of virtual circuits for a traffic class in a virtual path, and the deterministic multiplexing of different virtual paths leads to decoupling of the network dimensioning problem into the bandwidth estimation problem and the combined virtual path routing and capacity design problem. We discuss how bandwidth estimation can be done, then how the design problem can be solved by a decomposition algorithm by looking at the dual problem and using subgradient optimization. We provide computational results for realistic network traffic data to show the effectiveness of our approach. We show for the test problems considered, our approach does between 6% to 20% better than a local shortest-path heuristic. We also show that considering network dynamism through variation of traffic during the course of a day by doing dynamic bandwidth and virtual path reconfiguration can save between 10% and 14% in network design costs compared to a static network based on maximum busy hour traffic     

Sequential Monte Carlo inference of internal delays innonstationary data networks

On-line, spatially localized information about internal network performance can greatly assist dynamic routing algorithms and traffic transmission protocols. However, it is impractical to measure network traffic at all points in the network. A promising alternative is to measure only at the edge of the network and infer internal behavior from these measurements. We concentrate on the estimation and localization of internal delays based on end-to-end delay measurements from a source to receivers. We propose a sequential Monte Carlo (SMC) procedure capable of tracking nonstationary network behavior and estimating time-varying, internal delay characteristics. Simulation experiments demonstrate the performance of the SMC approach     

Analysis of gateway congestion in interconnected high-speed localnetworks

The effects of congestion on performance in interconnected high-speed local networks are investigated. The system studied uses network adapters as gateways to connect distributed local networks through a high-performance network link. Throughput measurements were determined by simulations of various combinations of link speeds, gateway buffering capacities, and local network traffic loads. The performance effects of several high-speed, local-network, bus-access protocols are investigated. Simulation model parameters are based on measurements of HYPERchannel networks     

A factor graph approach to link loss monitoring in wireless sensor networks

The highly stochastic nature of wireless environments makes it desirable to monitor link loss rates in wireless sensor networks. In a wireless sensor network, link loss monitoring is particularly supported by the data aggregation communication paradigm of network traffic: the data collecting node can infer link loss rates on all links in the network by exploiting whether packets from various sensors are received, and there is no need to actively inject probing packets for inference purposes. In this paper, we present a low complexity algorithmic framework for link loss monitoring based on the recent modeling and computational methodology of factor graphs. The proposed algorithm iteratively updates the estimates of link losses upon receiving (or detecting the loss of) recently sent packets by the sensors. The algorithm exhibits good performance and scalability, and can be easily adapted to different statistical models of networking scenarios. In particular, due to its low complexity, the algorithm is particularly suitable as a long-term monitoring facility.     

Network traffic prediction based on INGARCH model

In this paper, we introduce the integer-valued generalized autoregressive conditional heteroscedasticity (INGARCH) as a network traffic prediction model. As the INGARCH is known as a non-linear analytical model that could capture the characteristics of network traffic such as Poisson packet arrival and long-range dependence property, INGARCH seems to be an adequate model for network traffic prediction. Based on the investigation for the traffic arrival process in various network topologies including IoT and VANET, we could confirm that assuming the Poisson process as packet arrival works for some networks and environments of networks. The prediction model is generated by estimating parameters of the INGARCH process and predicting the Poisson parameters of future-steps ahead process using the conditional maximum likelihood estimation method and prediction procedure, respectively. Its performance is compared with those of three different models; autoregressive integrated moving average, GARCH, and long short-term memory recurrent neural network. Anonymized passive traffic traces provided by the Center for Applied Internet Data Analysis are used in the experiment. Numerical results show that the proposed model predicts better than the three models in terms of measurements used in prediction models. Based on the study, we can conclude the followings: INGARCH can capture the characteristics of network traffic better than other statistic models, it is more tractable than neural networks (NNs) overcoming the black-box nature of NNs, and the performances of some statistical models are comparable or even superior to those of NNs, especially when the data is insufficient to apply deep NNs.

     

Multi-tier cooperative caching in fog radio access network

Aiming at the problem of reducing the load of the backward link in the edge buffer and fog wireless access network technology,a multi-tier cooperative caching scheme in F-RAN was proposed to further reduce the backhaul traffic load.In particular,by considering the network topology,content popularity prediction and link capacity,the optimization problem was decomposed into knapsack subproblems in multi-tiers,and effective greedy algorithms were proposed to solve the corresponding subproblems.Simulation results show that the proposed multi-tier cooperative caching scheme can effectively reduce the backhaul traffic and achieve relatively high cache hit rate.     

Network delay tomography

The substantial overhead of performing internal network monitoring motivates techniques for inferring spatially localized information about performance using only end-to-end measurements. In this paper, we present a novel methodology for inferring the queuing delay distributions across internal links in the network based solely on unicast, end-to-end measurements. The major contributions are: 1) we formulate a measurement procedure for estimation and localization of delay distribution based on end-to-end packet pairs; 2) we develop a simple way to compute maximum likelihood estimates (MLEs) using the expectation-maximization (EM) algorithm; 3) we develop a new estimation methodology based on recently proposed nonparametric, wavelet-based density estimation method; and 4) we optimize the computational complexity of the EM algorithm by developing a new fast Fourier transform implementation. Realistic network simulations are carried out using network-level simulator ns-2 to demonstrate the accuracy of the estimation procedure.     

Distributed Nonlinear Integer Optimization for Data-Optical Internetworking

We present a novel approach for joint optical network provisioning and Internet protocol (IP) traffic engineering, in which the IP and optical networks collaboratively optimize a combined objective of network performance and lightpath provisioning cost. We develop a framework for distributed multilayer optimization. Our framework is built upon the IP-over-optical (IPO) overlay model, where each network domain has a limited view of the other. Our formulation allows the two domains to communicate and coordinate their decisions through minimal information exchange. Our solution is based on a novel application of Generalized Bender's Decomposition, which divides a difficult global optimization problem into tractable subproblems, each solved by a different domain. The procedure is iterative and converges to the global optimum. We present case studies to demonstrate the efficiency and applicability of our approach in various networking scenarios. Our work builds a foundation for “multilayer” grooming, which extends traditional grooming in the optical domain to include data networks. The data networks are active participants in the grooming process with intelligent homing of data traffic to optical gateways.     

Dynamic survivable mapping through reconfiguration in IP over WDM network

A new approach for network survivability problem in Intemet protocol （IP） over wavelength division multiplexing （WDM） optical network is proposed to enhance the IP layer restorability under physical link failure through logical topology reconfiguration. More specifically, after traffic arrival and departure, reconfiguring the logical topology correspondingly is helpful to minimize the traffic disruption after physical link failure. So, in this paper, this problem is proposed for first time and formulated as an integer linear programming （ILP） problem. And then, two heuristic algorithms are proposed. The performance of proposed algorithms have been evaluated through simulations, and the results show that reconfiguring the logical topology dynamically could achieve more than 20% improvement of the restorability of traffic in IP layer, but with acceptable resource cost.     

Network tomography from measured end-to-end delay covariance

End-to-end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. However, pinpointing the site of performance degradation from end-to-end measurements is a challenging problem. We show how end-to-end delay measurements of multicast traffic can be used to infer the under-lying logical multicast tree and the packet delay variance on each of its links. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through simulations, and analyze its failure modes and their probabilities.     

Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction

In large-scale dynamic communication networks, end systems cannot rely on the network itself to cooperate in characterizing its own behavior. This has prompted research activities on methods for inferring internal network behavior based on the external end-to-end network measurements. In particular, knowledge of the link losses and link delays inside the network is important for network management. However, it is impractical to directly measure packet losses or delays at every router. On the other hand, measuring end-to-end (from sources to destinations) losses or delays is relatively easy. We formulate the problems of link and delay estimation in a network based on end-to-end measurements as Bayesian inference problems and develop several Markov chain Monte Carlo (MCMC) algorithms to solve them. We show how these link loss and delay estimates can be used to predict point-to-point transfer control protocol (TCP) throughput in the network. We apply the proposed link loss and delay estimation algorithms, as well as the TCP throughput estimation algorithms, to data generated by the network simulator (ns-2) software and obtain good agreements between the theoretical results and the actual measurements.     

Resource allocation in satellite networks: certainty equivalent approaches versus sensitivity estimation algorithms

In this paper, we consider a resource allocation problem for a satellite network, where variations of fading conditions are added to those of traffic load. Since the capacity of the system is finite and divided in finite discrete portions, the resource allocation problem reveals to be a discrete stochastic programming one, which is typically NP‐hard. We propose a new approach based on the minimization over a discrete constraint set using an estimation of the gradient, obtained through a ‘relaxed continuous extension’ of the performance measure. The computation of the gradient estimation is based on the infinitesimal perturbation analysis technique, applied on a stochastic fluid model of the network. No closed‐forms of the performance measure, nor additional feedback concerning the state of the system, and very mild assumptions on the probabilistic properties about the statistical processes involved in the problem are requested. Such optimization approach is compared with a dynamic programming algorithm that maintains a perfect knowledge about the state of the satellite network (traffic load statistics and fading levels). The comparison shows that the sensitivity estimation capability of the proposed algorithm allows to maintain the optimal resource allocation in dynamic conditions and it is able to provide even better performance than the one reached by employing the dynamic programming approach. Copyright © 2004 John Wiley & Sons, Ltd.     

NetScope: traffic engineering for IP networks

Managing large IP networks requires an understanding of the current traffic flows, routing policies, and network configuration. However, the state of the art for managing IP networks involves manual configuration of each IP router, and traffic engineering based on limited measurements. The networking industry is sorely lacking in software systems that a large Internet service provider can use to support traffic measurement and network modeling, the underpinnings of effective traffic engineering. This article describes the AT&T Labs NetScope, a unified set of software tools for managing the performance of IP backbone networks. The key idea behind NetScope is to generate global views of the network on the basis of configuration and usage data associated with the individual network elements. Having created an appropriate global view, we are able to infer and visualize the networkwide implications of local changes in traffic, configuration, and control. Using NetScope, a network provider can experiment with changes in network configuration in a simulated environment rather than the operational network. In addition, the tool provides a sound framework for additional modules for network optimization and performance debugging. We demonstrate the capabilities of the tool through an example traffic engineering exercise of locating a heavily loaded link, identifying which traffic demands flow on the link, and changing the configuration of intradomain routing to reduce the congestion     

Adaptive bandwidth management in ATM networks

A framework for adaptive bandwidth management in ATM based networks is proposed. It is based on a layered approach which includes bandwidth allocation to virtual networks. The central concept of this approach is adaptive estimation of the effective bandwidth required, by connections carried in the network. To achieve reliable results the estimation process takes into account both the traffic source declarations and the connection superposition process measurements on the network links. This is done in an optimization framework provided by estimation theory. A study, based on a linear two-state Kalman filter, shows that the proposed approach provides good adaptation to undeclared changes in traffic parameters and that the network performance is significantly improved when compared to the effective bandwidth allocation based solely on the source parameters declarations. These features allow more relaxed source parameter declarations and at the same time permit less stringent source policing. Thus the two bottlenecks influencing bandwidth management in ATM networks can be significantly widened.     

多红外传感器融合系统数据关联算法

针对传统多红外传感器多目标多维分配数据关联模型在构造关联代价时未充分考虑位置估计不确定性所引入的随机误差问题,提出了一种可精确到二阶的高精度关联代价构造方法。取非线性量测函数泰勒展开式的前二阶项,将最小二乘估计的均值和方差信息代入得到伪量测信息的均值和方差,继而将伪量测与真实量测信息的统计距离作为最终的关联代价。最后对不同关联算法的正确率进行了实验对比,仿真结果表明修正后的关联代价能够更精准地反映出数据关联的可能性,基于该修正代价的关联算法较之其他关联算法可获得更好的关联性能。