1,721,092 research outputs found
On the Build-Up of Large Queues in a Queueing Model with Fractional Brownian Motion Input
No full textWe analyze the way in which large queues build up in the single-server fractional Brownian motion queueing model. The large deviations problem for the queue-length process can be rephrased as a moderate deviations problem for the underlying white noise. This framework allows us to obtain not only an asymptotic expression for the probability of overflow, but also the most likely path followed by the queue-length process to reach the overflow level and prediction of post-overflow behaviour. The model we consider has stationary increments: there is also a non-stationary version of fractional Brownian motion, introduced by Levy, which formed the basis for a similar study by Chang, Yao and Zajic. We compare our results with theirs, and illustrate the essential differences between the two models
A Probabilistic Counting Framework for Distributed Measurements
Full text linkThe technological maturity attained by general purpose processors and network interface cards makes today's commodity PCs viable and high performing alternatives to specialized hardware for deploying network devices, such as switches, routers, and generic middleboxes. In addition, the flexibility of the software solution seems to be perfectly in line with the emerging trend towards the data-plane programming abstractions brought by recent proposals such as Openflow and the P4 language. However, if programming abstractions provide the way elementary instructions (primitives) are combined together, the development of such processing primitives is left to the network programmer. Although the type of such functions is strongly domain specific, we can safely assume that the counting primitive is easily required in a great deal of practical contexts. This paper presents a counting framework based on probabilistic sketches and LogLog counters for estimating the cardinality of large multi-sets of data. The proposed data structure is designed to be fast and compact for ready use in the on-line chain of processing of network devices running at multi-gigabit speeds. The complete implementation is provided within the probabilistic data structures (pds) library which has been designed, developed, experimentally assessed, and released as open-source for free download. Although the paper specifically presents two possible use-cases, the pds library can be used in rather general scenarios, even outside the networking domain
Network Traffic Processing with PFQ
Full text linkThis paper presents Packet Family Queue (PFQ), a high-performance framework for packet processing designed to flexibly handle network applications parallelism and making traffic processing safe and easy. PFQ is an open-source module for the Linux kernel that combines software-accelerated packet I/O to in-kernel early stage packet processing and fine-grained distribution to network applications and physical devices. PFQ does not require any modification to network device drivers and exposes programming interfaces to multi-threaded applications natively designed to run on top of it, as well as to legacy monitoring tools using the pcap library. The results show that the flexibility and the backward compatibility provided by PFQ do not impact its processing performance that, in fact, reaches line rate figures in the cases of pure speed tests and real practical monitoring use cases on 10+ Gb/s links
Token bucket characterization of long-range dependent traffic
No full textThe token bucket characterization provides a deterministic yet concise representation of a traffic source. In this paper, we study the impact of the long-range dependence LRD) property of traf®c generated by today's multimedia applications on the optimal dimensioning of token bucket parameters. To this aim, we empirically illustrate the difference between the token bucket characteristics of traf®c exhibiting different degrees of time dependence but with identical macroscopic properties i.e. inter-arrival time and packet size distributions). In addition, we use a statistical model to analytically determine optimal token bucket parameters under various optimization criteria. The statistical model is based on fractional Brownian motion and takes LRD into account. We apply this model to several aggregated MPEG video sources. We then assess the validity of these analytic results by comparing them to empirical results. We conclude that the analytic approach presented here is effective in optimally sizing token buckets for LRD traffic, and promises to be applicable under different traffic conditions and for various optimization criteria
Testing alpha-stable processes in modelling broadband teletraffic
No full textThe paper presents the analysis of the applicability of alpha-stable processes in traffic modelling. This study is suggested by the goodness of alpha-stable processes in capturing not only the Long Range Dependence (LRD) of actual traffic, but also the heavy tailness of its marginal distribution. The relevance of this property is proved by means of discrete event simulations carried out considering two different data traffic sets, respectively related to a LAN-to-LAN intercomnection and entertainment video service. Errors in the est.mation of Hurst parameter and in the evaluationof queueing behaviour are highlighted either analytically and empirically by simulations. In particular the queueing simulations have emphasised the improvements in the performance forecast- ing introduced by the higher flexibility of a-stable model with respect to the widely used Fractional Brownian Mo- tion (FBM)
On traffic prediction for resource allocation: A Chebyshev bound based allocation scheme
No full textThe paper presents a predictive approach to network resource allocation techniques. The rationale of this work is to use measurements to estimate future traffic behavior by prediction, and to use such an estimation to define the amount of future network resources that will be required by the considered traffic.
In this framework, the paper presents the analysis and performance evaluation of classical and chaotic
techniques for network traffic prediction. The performance parameters considered in the analysis are: the accuracy of predictors in capturing the actual behavior of traffic; the computational complexity for a realistic integration of such predictors into experimental testbeds; and the responsiveness with respect to traffic pattern variations. The analysis results show that the classical normalized linear mean square predictor achieves a satisfactory trade-off among the above mentioned metrics as it presents a medium level of complexity while achieving high performance in terms of prediction accuracy and responsiveness to network traffic changes. Then, using the normalized linear mean square predictor, we derive a bandwidth allocation strategy, named statistical delay bound (SDB), which guarantees a probabilistic bound on the delay experienced by packets traversing a network node. The paper presents the performance analysis of SDB showing that, in spite of the simplicity of the adopted predictive algorithm, the proposed measurement based technique allows to fulfill the project requirements and candidates for actual experimentation into prototypal routers which supports QoS mechanisms
Blooming trees: Space-efficient structures for data representation
No full textA Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. A Counting Bloom Filter (CBF) allows the same operations on dynamical sets that can be updated via insertions and deletions with larger memory requirements. This paper presents a novel hierarchical data structure, called Blooming Tree, that replicates the functionalities of a CBF with lower memory consumption and tunable false positive probability. The hierarchical multi-layer design of Blooming Trees allows for distributing the structure in different memory levels, thus exploiting small but fast on-chip memories for most frequently accessed substructures. The proposed algorithm is compared to previous existing schemes on a target platform: Intel IXP2XXX Network Processors (NPs)
Randomized packet filtering through specialized partitioning of rulesets
Full text linkA key issue in high speed traffic processing is to immediately detect potentially interesting packets. At very high speed, this operation is particularly crucial as filtering packets close to the wire relieves real applications from handling large volumes of (uninteresting) data. This paper proposes a fast and randomized approach to packet filtering based on partitioning rule databases for their storage in fast and compact Bloom filters that can be placed in fast cache memory. Database partitioning is obtained by a specially tailored clustering algorithm and the results show that even large rulesets can be divided into a limited number of partitions and accommodated in reasonably small Bloom filters. © 1997-2012 IEEE
On the relevance of correlation dependencies in ON/OFF characterization of broadband traffic
No full textThe paper presents joint measurements of IP and ATM traffic over an MPOA based campus network. The search for parsimonious realistic modeling of heterogeneous aggregated traffic has led to the generalization of on/off modeling schemes. Even a single on/off pattern with Pareto-geometric distributions of the sojourn times in each state determines a hyperbolic decay of the autocovariance function corresponding to long range dependence (LRIB). Hence, adequate on/off models can fit real traces corresponding to the multiplexing of several heterogeneous connections. In the paper, the on/off behavior of the traffic is evidenced at the ATM level. The relevant feature of the traces is that either the on and the off sojourn times could be well approximated by a light tailed distribution. The observed LRD behavior is due to the presence of correlation in the sequence of on (as well as off) periods lengths. In order to confirm this hypothesis, different synthetic traces were considered, verifying the LRD behavior by means of wavelet analysis. Implications of such state correlations on queueing behavior are then compared by means of discrete event simulation
- …
