Perturbation analysis for online control and optimization of stochastic fluid models

Uses stochastic fluid models (SFMs) for control and optimization (rather than performance analysis) of communication networks, focusing on problems of buffer control. We derive gradient estimators for packet loss and workload related performance metrics with respect to threshold parameters. These estimators are shown to be unbiased and directly observable from a sample path without any knowledge of underlying stochastic characteristics, including traffic and processing rates (i.e., they are nonparametric). This renders them computable in online environments and easily implementable for network management and control. We further demonstrate their use in buffer control problems where our SFM-based estimators are evaluated based on data from an actual system.     

Perturbation Analysis of Multiclass Stochastic Fluid Models

We use a stochastic fluid model (SFM) to capture the operation of finite-capacity queueing systems with multiple customer classes. We derive gradient estimators for class-dependent loss and workload related performance metrics with respect to any one of several threshold parameters used for buffer control. These estimators are shown to be unbiased and directly observable from a sample path without any knowledge of underlying stochastic characteristics of the traffic processes. This renders them computable in on-line environments and easily implementable in settings such as communication networks.     

Perturbation analysis and optimization of stochastic flow networks

We consider a stochastic fluid model of a network consisting of several single-class nodes in tandem and perform perturbation analysis for the node queue contents and associated event times with respect to a threshold parameter at the first node. We then derive infinitesimal perturbation analysis (IPA) derivative estimators for loss and buffer occupancy performance metrics with respect to this parameter and show that these estimators are unbiased. We also show that the estimators depend only on data directly observable from a sample path of the actual underlying discrete event system, without any knowledge of the stochastic characteristics of the random processes involved. This renders them computable in online environments and easily implementable for network management and optimization. This is illustrated by combining the IPA estimators with standard gradient based stochastic optimization methods and providing simulation examples.     

On-line control of the threshold policy parameter for multiclass systems

Motivated by the problem of Quality of Service (QoS) provisioning, this paper investigates a system with two classes of traffic and addresses the problem of dynamically controlling the buffer threshold used with the threshold policy, such that an objective function is optimized. For the analysis, a Stochastic Fluid Model (SFM) is used to derive unbiased sensitivity estimators of various metrics (workload, loss, throughput and packet expiration) with respect to the buffer threshold. These estimators are computed using information obtained from the sample path of the “real” discrete event system. Thus, one can use these estimators together with stochastic approximation techniques in order to maintain the system at a near-optimum point despite any changes in the incoming traffic or the transmission capacity of the network.     

Perturbation analysis of stochastic fluid models with respect to the fluid arrival process

The deployment of network applications (e.g., multimedia and other real time applications) has put extra pressure on network scarce resources (bandwidth and buffers) thus generating a need for effective resource allocation and management. In this paper we adopt a stochastic fluid model (SFM) framework and derive sensitivity estimators for three performance measures of interest (workload, throughput and loss volume) with respect to the fluid inflow process parameters. The motivation is to use the sensitivity estimators for dynamic control and optimisation of the systems performance. Subsequently these estimators are evaluated based on data observed from a single sample path of the discrete-event system and are used to dynamically control the input process to the system allowing the network to work continuously at an optimal or near optimal point. The proposed analysis naturally leads to a distributed algorithm for evaluating the propagation of perturbations in a network (e.g., due to changes in the buffer size of upstream nodes).     

Perturbation analysis of feedback-controlled stochastic flow systems

Stochastic flow systems arise naturally or as abstractions of discrete-event systems (DESs), referred to as stochastic flow models (SFMs). In this paper, we consider such systems operating with a feedback control mechanism, building on earlier work that has studied such SFMs without any feedback. Using infinitesimal perturbation analysis, we derive gradient estimators for loss and workload related performance metrics with respect to threshold parameters used for buffer control. These estimators are shown to be unbiased. They are also shown to depend only on data observable from a sample path of the actual DES. This renders them computable in on-line environments and easily implementable for control and performance optimization purposes. In the case of linear feedback, we further show that the estimators are nonparametric. Finally, we illustrate the use of these estimators in network control by combining them with standard gradient-based stochastic optimization schemes and providing several simulation-based examples.     

网络结点缓冲区动态占用特性分析

针对网络结点的阻塞控制与结点缓冲区的关系问题,利用交叉开关网络结构及其非阻塞特性,采用概率论分析方法,结合网络流量的非线性特征,对通过结点缓冲区的流量以及缓冲区的动态占用情况进行了分析,得出了缓冲区动态占用情况的定量描述函数,并作了相关的证明和验证,为基于网络结点缓冲区占用情况的流量控制建立了一定的基础,有利于结点缓冲区优化控制机制的建立,提高结点缓冲区的适应能力,降低因为缓冲区不适应流量而造成的阻塞概率。     

基于FARIMA的网络建模与性能分析

给出了利用FARIMA模型进行建模、拟合实际网络流量的方法和参数估计的具体步骤,研究了长短相关对网络性能的影响.研究结果表明,不论长相关还是短相关,FARIMA模型对实际业务拟合二者都非常接近,当缓存较小时,网络性能将由短相关特性支配,而且随着缓存增加,长相关业务下系统性能的衰减要比短相关业务下衰减的慢,这些发现对今后网络设计性能研究具有重要的参考价值.     

A neural network controller for congestion control in ATM multiplexers

This paper presents and adaptive approach to the problem of congestion control arising at the User-to Network Interface (UNI) of an ATM multiplexer. We view the ATM multiplexer as a non-linear stochastic system whose dynamics are ill-defined. Real-time measurements of the arrival rate process and the queueing process, are used to identify, and minimize congestion episodes. The performance of the system is evaluated using a performance-index function which is a quantative measure of “how well” the system is performing. A three-layers backpropagation neural network controller generates a signal that attempts to minimize congestion without degrading the quality of the traffic. During periods of buffer over-load the control signal, adaptively, modulates the arrival process such that its peak-rate is throttled-down. As soon as congestion is terminated, the control signal is adjusted such that the coding rates are restored back to their original values. Adaptability is achieved by continuously adjusting the weights of the neural network controller such that the performance of the system, measured by its performance index function, is maximized over a certain optimization period. The performance index function is defined in terms of two main objectives: (1) to minimize the cell loss rate (CLR), i.e., minimize congestion episodes, and (2) to maintain the quality of the video/audio traffic by maintaining its original source coding rate. The neural network learning process can be viewed as a specialized form of reinforcement learning in the sense that the control signal is reinforced if it tends to maximize the performance index function. Performance evaluation results prove that this approach is effective in controlling congestion while maintaining the quality of the traffic.     

An algorithm for architecture partitioning in high-speed networks with bursty traffic

This paper analyzes the performance of a switching architecture. The performance measures include the elapsed time of packet transfer and the waiting time to begin transfer. The architecture is partitioned depending on the type of network used and the expected traffic in the network. Every partition has a switch with a buffer that can absorb surges of bursty traffic within the network partition. The buffer size depends on the type of the network and incoming traffic. The partition size depends on the network bandwidth, network traffic, packet size and buffer size. Examples of different networks are used to show the applications of the model. The results show that the elapsed time of packet switch transfer depends exponentially on the number of partitions in the network.     

A simulation study of bursty data traffic with hybrid source smoothing in an ATM node

In this paper, we study the mean delay and maximum buffer requirements at different levels of burstiness for highly bursty data traffic in an ATM node. This performance study is done via an event-driven simulation program which considers both real-time and data traffic. We assume that data traffic is loss-sensitive. A large buffer (fat bucket) is allocated to data traffic to accommodate sudden long burst of cells. Real-time traffic is delay-sensitive. We impose input traffic shaping on real-time traffic using a leaky-bucket based input rate control method. Channel capacity is allocated based on the average arrival rate of each input source to maximize the utilization of channel capacity. Simulation results show that both the maximum buffer requirements and mean node delay for data traffic are directly proportional to the burstiness of its input traffic. Results for mean node delay and cell loss probability of real-time traffic are also analyzed. The simulation program is written in C++ and has been verified using the zero mean statistics concept by comparing simulation results to known theoretical or observed results.     

网络流量长相关特性的滑窗时变估计算法

网络流量在动态演进过程中呈现出长相关(LRD)特性,定量描述LRD特性是网络行为研究的重要问题之一.由于传统LRD估计算法采用全域求和平均,造成序列中突发信息损失,致使传统算法均不能在复杂条件下有效估计LRD.在引入时变Hurst指数函数的概念后,提出了时域滑窗时变Hurst(SWTV-H)估计算法.SWTV-H算法在某一分辨率水平上给出局域内Hurst指数的估计,并通过局域时移实现流量序列全域内LRD趋势的动态估计.分别用仿真以及真实网络流量数据对其有效性进行了验证,与传统算法的估计结果相比,SWTV-H算法能更准确估计LRD特性,且具有更好的鲁棒性.     

Fuzzy-based rate control for real-time MPEG video

We propose a fuzzy logic-based control scheme for real-time motion picture expert group (MPEG) video to avoid long delay or excessive loss at the user-network interface (UNI) in an asynchronous transfer mode (ATM) network. The system consists of a shaper whose role is to smooth the MPEG output traffic to reduce the burstiness of the video stream. The input and output rates of the shaper buffer are controlled by two fuzzy logic-based controllers. To avoid a long delay at the shaper, the first controller aims to tune the output rate of the shaper in the video frame time scale based on the number of available transmission credits at the UNI and the occupancy of the shaper's buffer. Based on the average occupancy of the shaper's buffer and its variance, the second controller tunes the input rate to the shaper over a much larger time scale by applying a closed-loop MPEG encoding scheme. With this approach, the traffic enters the network at an almost constant bit rate (with a very small variation) allowing simple network management functions such as admission control and bandwidth allocation, while guaranteeing a relatively constant video quality since the encoding rate is changed only in critical periods when the shaper buffer “threatens” to overflow. The performance of the proposed scheme is evaluated through numerical tests on real video sequences     

Hybrid fluid modeling approach for performance analysis of P2P live video streaming systems

In this paper a hybrid modeling approach with different modeling formalisms and solution methods is employed in order to analyze the performance of peer to peer live video streaming systems. We conjointly use queuing networks and Fluid Stochastic Petri Nets, developing several performance models to analyze the behavior of rather complex systems. The models account for: network topology, peer churn, scalability, peer average group size, peer upload bandwidth heterogeneity and video buffering, while introducing several features unconsidered in previous performance models, such as: admission control for lower contributing peers, control traffic overhead and internet traffic packet loss. Our analytical and simulation results disclose the optimum number of peers in a neighborhood, the minimum required server upload bandwidth, the optimal buffer size and the influence of control traffic overhead. The analysis reveals the existence of a performance switch-point (i.e. threshold) up to which system scaling is beneficial, whereas performance steeply decreases thereafter. Several degrees of degraded service are introduced to explore performance with arbitrary percentage of lost video frames and provide support for protocols that use scalable video coding techniques. We also find that implementation of admission control does not improve performance and may discourage new peers if waiting times for joining the system increase.     

Buffer and Delay Bounds in High Radix Interconnection Networks

We apply recent results in queueing theory to propose a methodology for bounding the buffer depth and packet delay in high radix interconnection networks. While most work in interconnection networks has been focused on the throughput and average latency in such systems, few studies have been done providing statistical guarantees for buffer depth and packet delays. These parameters are key in the design and performance of a network. We present a methodology for calculating such bounds for a practical high radix network and through extensive simulations show its effectiveness for both bursty and non-bursty injection traffic. Our results suggest that modest speedups and buffer depths enable reliable networks without flow control to be constructed.     

RCSP and stop-and-go: a comparison of two non-work-conserving disciplines for supporting multimedia communication

To support emerging real-time applications, high-speed integrated services networks must provide end-to-end performance guarantees on a per-connection basis in a networking environment. Resource management algorithms must accommodate traffic that may get burstier as it traverses the network due to complex interactions among packet streams at each switch. To address this problem, several non-work-conserving packet-service disciplines have been proposed. Non-work-conserving servers may be idle and hold packets under certain conditions, to reconstruct, fully or partially, the traffic pattern of the original source inside the network and prevent the traffic from becoming burstier. We compare two non-work-conserving service disciplines. Stop-and-go uses a multilevel framing strategy to allocate resources in a single switch and to ensure traffic smoothness throughout the network. Rate controlled static priority (RCSP) decouples the server functions with two components: (1) a regulator to control traffic distortion introduced by multiplexing effects and load fluctuations in previous servers, and 2) a static priority scheduler to multiplex the regulated traffic. We compare the two service disciplines in terms of traffic specification, scheduling mechanism, buffer space requirement, end-to-end delay characteristics, connection admission-control algorithms, and achievable network utilization. The comparison is first done analytically, and then empirically by using two 10-min traces of MPEG compressed video.     

Simulation of dynamic input buffer space in multistage interconnection networks

This paper presents a simulation study of a new dynamic allocation of input buffer space in multistage interconnection networks (MINs). MINs are composed of an interconnected set of switching elements (SEs), connected in a specific topology. The SEs are composed of input and output buffers which are used to store received and forwarded packets, respectively. The performance of these networks depends on the design of these internal buffers and the clock mechanism in synchronous MINs. Various cycle models exist which include the big cycle, small cycle and the smart cycle, each of which provides a more efficient cycle timing. The smart cycle model achieves a superior performance by using output buffers and acknowledgement. However, it suffers from lost and out-of-order packets at high traffic loads. This paper, presents a variation of the smart cycle model, whereby, the input buffer space of each SE is allocated dynamically as a function of traffic load, in order to overcome the above-mentioned drawbacks. A shared buffer pool is provided, which supplies the required input buffer space as required by each SE. Simulation results are presented, which show the required buffer pool for various network sizes and for different network loads. Also, comparison with a static allocation scheme shows an increased network throughput, and the elimination of lost and out-of-order packets at high traffic loads.     

Dynamic buffer allocation in an ATM switch

Efficient and fair use of buffer space in an Asynchronous Transfer Mode (ATM) switch is essential to gain high throughput and low cell loss performance from the network. In this paper a shared buffer architecture associated with threshold-based virtual partition among output ports is proposed. Thresholds are updated based on traffic characteristics on each outgoing link, so as to adapt to traffic loads. The system behavior under varying traffic patterns is investigated via simulation; cell loss rate is the quality of service (QoS) measure used in this study. Our study shows that the threshold based dynamic buffer allocation scheme ensures a fair share of the buffer space even under bursty loading conditions.     

Input buffer requirements for round robin polling systems

A packet switched network that can be modeled as a round robin polling system with nonzero switchover times is considered. The input traffic is assumed to obey the (σ, ) regularity conditions recently proposed by Cruz [IEEE Trans. Inform. Theory 37(1) (1991) 114–141]. These conditions are particularly applicable to traffic from open loop flow control mechanisms, such as the leaky bucket. For partially gated service, upper and lower bounds are provided for buffer requirements to insure no data loss. The bounds are extended to gated and exhaustive service and are modified to provide bounds on guaranteed network delays. Using the bounds, it is demonstrated that partially gated service requires nearly minimal buffering when incoming traffic approaches the capacity of the network. It is also demonstrated that open loop flow control can improve the buffer requirements and guaranteed delays of the network significantly.     

多链路时延反馈共享令牌流量拥塞控制

流量调度的目标是提高网络资源的利用率,改善网络应用的性能,针对多链路环境下流量控制机制存在的问题,设计了一种多链路共享令牌缓冲池流量调度模型,分析了链路中数据传输时延特点,提出一种基于时延反馈信息的共享令牌流量拥塞控制算法,根据链路时延选择函数对多链路进行反馈流量调度。实验结果表明,该算法可以有效地减少数据在链路访问延时,而且链路流量的平滑性、带宽利用率等都比其他传统调度算法要好,适合于高性能宽带接入链路流量控制的应用。