Performance Analysis of a DEKF for Available Bandwidth Measurement

Abstract

The paper presents a characterisation analysis of a measurement algorithm based on a Discrete-time Extended Kalman Filter (DEKF), which has recently been proposed for the estimation and tracking of end-to-end available bandwidth. The analysis is carried out by means of simulations for different rates of variations of the available bandwidth and permits assessing the performance of the measurement algorithm for different values of the filter parameters, that is, the covariance matrixes of the measurement and process noise.

Academic Editor:Muhammad Taher Abuelma'atti

Department of Engineering, University of Naples "Parthenope", Centro Direzionale Isola C4, 80143 Naples, Italy

Received 4 December 2015; Revised 29 January 2016; Accepted 3 February 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The available bandwidth (AB) of a path, also known as unused bandwidth, is a key network metric [1]. Its estimate is used for route selection, quality of service (QoS) verification, and traffic engineering. More recently, AB estimation has increased its importance with respect to new demanding scenarios like cloud computing, voice-over-IP (VoIP), and multimedia networks, where support tools for traffic shaping and traffic policing as well as developing network management strategies are crucial [2-7]. Moreover, available bandwidth can directly affect the performance of distributed systems and clocks [8, 9].

AB of a link [figure omitted; refer to PDF] is defined as the unused or spare capacity of [figure omitted; refer to PDF] during the time interval [figure omitted; refer to PDF] . It depends on underlying transmission technology and propagation medium as well as the traffic load that occurs in the considered time interval [1, 10]. Traffic load is a time-varying metric and is related to the network utilization. In detail, assuming that at a specific instant [figure omitted; refer to PDF] the channel is busy or idle, the instantaneous network utilization is referred to as [figure omitted; refer to PDF] and takes value 1 or 0. The average utilization of a link [figure omitted; refer to PDF] in the period [figure omitted; refer to PDF] is defined as follows: [figure omitted; refer to PDF]

The AB at a given instant [figure omitted; refer to PDF] of the link [figure omitted; refer to PDF] can be thus expressed as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the capacity of [figure omitted; refer to PDF] [1, 10]. Finally, AB of an end-to-end path [figure omitted; refer to PDF] is given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the number of hops along [figure omitted; refer to PDF] and [figure omitted; refer to PDF] represents AB of the [figure omitted; refer to PDF] th link along [figure omitted; refer to PDF] . In detail, the link of [figure omitted; refer to PDF] with the minimum AB is referred to as tight link, while the link with the minimum capacity is referred to as narrow link. However, the term bottleneck in general refers to the link of a path that is characterised by the minimum AB and capacity.

The literature presents several tools to estimate AB of an end-to-end path, which are classified according to the underlying models that can be classified in PGM and PRM-based models. The PGM-based model is generally preferred compared to PRM model for its less intrusiveness and, generally, ease of implementation, although, the latter is more accurate. However, the literature presents several pieces of work based on the PGM model that loosen some of the underlying hypothesis with the ultimate purpose of evaluating its performance in more demanding scenarios.

The paper presents an analysis of the performance of a DEKF as a support tool for tracking abrupt AB changes during the measurement time presented in [11]. Abrupt changes during the measurement time de facto represent a loosening of the underlying PGM-based model's hypothesis of low variation of the AB during the measurement time. The presented characterisation study is performed in terms of covariance matrix of the process noise and measurement noise for different speed of the AB variations, in order to highlight limits, performance, and applicability of the method. The analysis provides useful results for the estimation of the most appropriate values for both aforementioned covariance matrixes.

The paper is organised as follows. Section 2 describes the PRM and PGM models and introduces the fundamentals of the DEKF under analysis. Section 3 gives details on the simulations that have been carried out. Section 4 presents and discusses the results of the simulations. Finally, Section 5 gives the conclusions.

2. Related Work

2.1. Available Bandwidth Estimation

Several measurement methodologies and tools have been developed and are available in the literature and on the market [12] for the estimation of the end-to-end AB of a network path. They can be classified in PGM-based (Probe Gap Model) methods and PRM-based (Probe Rate Model) methods. PGM-based tools implement the so-called iterative probing approach, whereas PRM-based tools are based on direct probing.

An implementation of PRM exploits a self-congestion of end-to-end path. In detail, the system sends a train of packets whose probing packet rate is decreased as it reaches AB of the path, and then a queue starts building up at the bottleneck link. The bottleneck link is in general referred to as the link of the path with the minimum AB and capacity [1]. The queue increases the probing packet rate at the receiver node which gets lower than the probing packet rate at the sender node. Tuning the probing packet rate of the train of packets at the sender node with the probing packet rate at the receiver node makes it possible to calculate the AB of the path, which is by definition the AB of the bottleneck link. Examples of applications based on the PRM are Pathload [13], Pathchirp [14], and PTR/IGI [15]. An implementation based on the PGM sends a pair of packets (but it can also be a train of packets [1]) separated by an initial time interval [figure omitted; refer to PDF] at the sender node; then the receiver node receives a pair of packets separated by an increased time interval [figure omitted; refer to PDF] . Like the PRM, also the PGM requires that the routers along the end-to-end path implement a FIFO queue and the cross traffic to be constant (it is also called path persistent cross traffic) and that it slowly changes during the measurement time. The time interval [figure omitted; refer to PDF] at the receiver node represents the time interval of the bottleneck link to transmit the pair of packets and the cross traffic that occurs between them. AB of the bottleneck is calculated according the following formula: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the capacity of the bottleneck link. It is worth noting that the PGM requires that there is a single bottleneck along the end-to-end path. In other words, this means that the tight link (which is the link with the minimum AB) matches the narrow link (which is the link with the minimum capacity) [1]. The probing packets rate at the first hop is set equal to the capacity of the bottleneck. Examples of measurement tools based on PGM are Delphi [16] and Spruce [10].

PGM-based measurement methodologies are simple to implement and generally less intrusive than PRM-based ones. However, due to their underlying assumptions, such methodologies can suffer from reduced accuracy.

Both PGM and PRM models take the following hypothesis: (i) there are no L2 (Layer-2) devices, such as switches, of the OSI (Open System Interconnected) model along the end-to-end path, (ii) the routers implement FIFO (First-In-First-Out) queues, and (iii) average rate of the path persistent cross traffic changes slowly and it is constant during the measurement time. Moreover, the PGM model requires that there is one bottleneck along the path, which means that the narrow link matches with the tight link [10].

The work presented in [17] showed that PGM-based tools can underestimate the AB in case the condition of having a constant traffic along the whole path is not met. The paper demonstrates that the measurement model is strongly affected by the position of the bottleneck link in the path and the model uncertainty can lead to nonnegligible measurement error. In particular, in case of one-hop persistent traffic, which means that the cross traffic rate changes at each hop, the measurement equation turns into a different expression. The model modification depends not only on the position of the bottleneck in the path but also on the initial rate of probing packets. In case the bottleneck is not the first hop, the probing packet rate could happen to be increased at the hops preceding the bottleneck, thus resulting in a variation of the one-hop probing packet.

Recently, a measurement method based on DEKF to track the AB in presence of abrupt variations due to variations of path persistent cross traffic over time was presented [11]. The method is based on a PGM and specifically on the model presented in [10]. Although a few experiments are reported in [11], no performance analysis of the filter with respect to its parameters and/or the speed of AB variations is given.

2.2. Fundamentals of Kalman Filtering

The Kalman filter solves the problem of estimating the state [figure omitted; refer to PDF] of a discrete-time controlled process that is governed by the linear stochastic difference equation [18, 19]: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the state transition matrix of the process, [figure omitted; refer to PDF] ties the input vector with the state vector, [figure omitted; refer to PDF] represents the input vector at the step [figure omitted; refer to PDF] , [figure omitted; refer to PDF] represents the measurements carried out on the system at the step [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is the measurement matrix. [figure omitted; refer to PDF] and [figure omitted; refer to PDF] represent, respectively, the process and the measurement noise, which are assumed to be statistically independent of each other and have normal probability distribution: [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are, respectively, the covariance matrix of the process and measurement noise. In case, the system is described by nonlinear stochastic difference equations as the following: [figure omitted; refer to PDF]

Then, the above system can be described as a DEKF, where the functions [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are approximated to their first-order Taylor's series expansions. The state vector estimation at the step [figure omitted; refer to PDF] is given by first calculating the following predict equations: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] [figure omitted; refer to PDF] being the Jacobian matrix of partial derivatives of [figure omitted; refer to PDF] with respect to [figure omitted; refer to PDF] and represents the state transition matrix and [figure omitted; refer to PDF] being the Jacobian matrix of partial derivatives of [figure omitted; refer to PDF] with respect to [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is the original covariance matrix of the process noise at the step [figure omitted; refer to PDF] and it is assumed to be a constant and therefore the subscript is dropped in the rest of the paper.

The state vector estimation is, then, given by the following measurements update equations: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] represents the error covariance matrix at the step [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] is the a priori error covariance matrix).

The DEKF presented in [11] is intended to track AB variations during the measurement time in order to provide more accurate AB measurements, which according to (5) can be formalised as follows: (5) turn into the following: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] represents the state equation, [figure omitted; refer to PDF] represents the measurement equation, [figure omitted; refer to PDF] is the initial probing rate, and [figure omitted; refer to PDF] the capacity of the bottleneck link.

3. Simulation Setup

The analysis has been carried out on a dataset of 60 items, each one containing several scenarios simulated by using MATLAB. Each scenario is made up of 1440 samples. In detail, the algorithm first creates the simulation environment, during which it randomly generates 8 hops with different link capacity and AB and the bottleneck link along with all its AB and capacity and then it calculates the AB variation for the bottleneck.

After the configuration environment is ready, the algorithm starts the DEFK. The same configuration is run for several values of slope variation and values of the covariance matrixes of the process noise and measurement noise.

Regarding the AB variation, the algorithm starts from the AB of the bottleneck and then decreases it till reaching a lower AB calculated during the configuration phase. The slope variation is simulated by using two slopes, that is, two different numbers of samples to represent the transition: 15 samples, which represent an abrupt variation, and 360 samples. Examples of outputs of the algorithm for 15 and 360 samples are, respectively, shown in Figures 1 and 2. In detail, the two figures show AB estimated by the DEKF against the actual AB value by using a value of the covariance matrix of the process noise equal to 10¹⁰ and a value of the covariance matrix of the measurement noise equal to 10^-12 . The simulation is carried out for several values of the covariance matrix of the process noise [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] and measurement noise [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . The algorithm performance is evaluated in terms of percentage relative error, which is defined as [figure omitted; refer to PDF]

Figure 1: The AB estimated by DEKF against the actual AB value for (a) an abrupt AB variation and (b) a slower variation.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

Figure 2: Comparison of the DEKF's performance for an abrupt AB variation for a value of the covariance matrix of the measurement noise equal to 10^-12 and for two different values of the covariance matrix of the process noise: (a) 10⁹ and (b) 10¹¹ .

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

The percentage relative error between normal values provided by the PGM ( [figure omitted; refer to PDF] ) and the AB estimates by the DEKF ( [figure omitted; refer to PDF] ) provides information about how close the estimate is to eventual outcomes and permits tracking the accuracy of the AB estimation.

4. Results

The results are presented in Figures 3 and 4. The former shows the 3D bars plots of the percentage of the relative errors falling below three given thresholds. In particular such thresholds are 1% (Figures 3(a) and 3(b)), 5% (Figures 3(c) and 3(d)), and 10% (Figures 3(e) and 3(f)) for abrupt AB variations of 15 samples and slower AB variations of 360 samples. Figure 4 shows the 3D bars plots of the percentage of the relative errors for the same aforementioned thresholds and slope variations, which are limited to the AB transitions; that is, only related errors observed during the AB transition are considered to calculate these percentages.

Figure 3: Percentage of relative errors that are below different thresholds [figure omitted; refer to PDF] for fast AB variations (a, c, and e) and slow AB variations (b, d, and f). [figure omitted; refer to PDF] % in (a) and (b), [figure omitted; refer to PDF] % in (c) and (d), and [figure omitted; refer to PDF] % in (e) and (f).

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

(f) [figure omitted; refer to PDF]

Figure 4: Percentage of relative errors that are below different thresholds [figure omitted; refer to PDF] for fast AB variations (a, c, and e) and slow AB variations (b, d, and f). [figure omitted; refer to PDF] % in (a) and (b), [figure omitted; refer to PDF] % in (c) and (d), and [figure omitted; refer to PDF] % in (e) and (f).

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

(f) [figure omitted; refer to PDF]

The relative errors are plotted over a plan whose axes represent the covariance matrixes of the measurement and process noise, respectively. In detail, each bar represents the percentage of errors calculated according to (12) that fall below the considered threshold.

It is worth noting that all results depicted in Figures 3 and 4 represent average values over the 60 datasets considered for the simulations.

From Figure 3, we can observe that the percentage of the relative errors falling in the considered thresholds rises as the value of the covariance matrix of measurement noise decreases and the value of the covariance matrix of the process noise rises. In other words, the measurement algorithm exhibits better performance for high values of the covariance matrix of the process noise. The percentage of the relative error improves as the thresholds rises.

It is worth noting that the process noise of the DEKF proposed in [11] represents a degree of freedom and it can be chosen according to the covariance matrix of the measurement noise for which the DEKF algorithm shows the best performance. Therefore, once the value of the covariance matrix of the measurement noise is fixed, which depends on the network, the covariance matrix of the process noise can be chosen according to the 3D bar which shows the greatest percentage of the errors lower than the considered threshold. However, as shown in Figure 4, the performance of the algorithm gets worse for low values of the covariance matrix of the process noise during AB variations. Such a poor performance is due to the fact that DEKF is not able to follow the AB variation for low values of the covariance matrix of the process noise.

An example is given in Figure 2, which shows AB estimated by the DEKF against its nominal value when the covariance matrix of the measurement noise equals 10^-12 and for two values of the covariance matrix, which are, respectively, 10⁹ (Figure 2(a)) and 10¹¹ (Figure 2(b)), during an abrupt AB variation. By comparing the two figures, it is possible to notice that the algorithm is not able to track the abrupt variation in case of a lower value of the covariance matrix of the process noise. Further confirmation is provided by comparing the figures in first column shown in Figure 4, which represent abrupt AB variations, with the figures in second column of the same figure, which represent a slower AB variation.

5. Conclusion

The paper has presented a characterisation analysis of the performance of a DEFK applied to a PGM-based measurement method for tracking AB variations in case of the fact that cross traffic is not path-persistent and exhibits both slow and abrupt variation over time.

The paper has highlighted that the covariance matrix of the process noise for the DEKF can be properly chosen in order to decrease the measurement noise and, finally, achieve a better AB estimation. Moreover, the paper has shown that, for fixed values of the covariance matrix of the measurement noise, the performance of the DEKF, in terms of relative error, improves as the value of the covariance matrix of the process noise decreases. However, the DEKF algorithm is not able to follow abrupt AB variations as the value of the covariance matrix of the process noise rises.

Further research activities will focus on the performance assessment of the measurement method on real networks and for different patterns of available bandwidth variations.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] R. S. Prasad, C. Dovrolis, M. Murray, K. Claffy, "Bandwidth estimation: metrics, measurement techniques, and tools," IEEE Network , vol. 17, no. 6, pp. 27-35, 2003.

[2] D. M. Batista, L. J. Chaves, N. L. S. da Fonseca, A. Ziviani, "Performance analysis of available bandwidth estimation tools for grid networks," in Proceedings of the IEEE 14th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD '09), pp. 1-5, Pisa, Italy, June 2009.

[3] T. A. L. Genez, L. F. Bittencourt, N. L. S. Da Fonseca, E. R. M. Madeira, "Refining the estimation of the available bandwidth in inter-cloud links for task scheduling," in Proceedings of the IEEE Global Communications Conference (GLOBECOM '14), pp. 1127-1132, Austin, Tex, USA, December 2014.

[4] T. A. L. Genez, L. F. Bittencourt, N. L. S. Da Fonseca, E. R. M. Madeira, "Estimation of the available bandwidth in inter-cloud links for task scheduling in hybrid clouds," IEEE Transactions on Cloud Computing , 2015.

[5] M. Imai, Y. Sugizaki, K. Asatani, "A new estimation method using RTT for available bandwidth of a bottleneck link," in Proceedings of the IEEE 27th International Conference on Information Networking (ICOIN '13), pp. 529-534, IEEE, Bangkok, Thailand, January 2013.

[6] A. Mahanti, C. Williamsonm, M. Arlittm, A. Mahantit, "Comparing wired-side and wireless-side WLAN monitoring techniques: a case study," in Proceedings of the 32nd IEEE Conference on Local Computer Networks (LCN '07), pp. 901-910, Dublin, Ireland, October 2007.

[7] N. Basher, A. Mahanti, A. Mahanti, C. Williamson, M. Arlitt, "A comparative analysis of web and peer-to-peer traffic," in Proceedings of the 17th International Conference on World Wide Web (WWW '08), pp. 287-296, Beijing, China, April 2008.

[8] A. Bondavalli, A. Ceccarelli, F. Brancati, D. Santoro, M. Vadursi, "Differential analysis of Operating System indicators for anomaly detection in dependable systems: an experimental study," Measurement , vol. 80, pp. 229-240, 2016.

[9] A. Bondavalli, F. Brancati, A. Ceccarelli, L. Falai, M. Vadursi, "Resilient estimation of synchronisation uncertainty through software clocks," International Journal of Critical Computer-Based Systems , vol. 4, no. 4, pp. 301-322, 2013.

[10] J. Strauss, D. Katabi, F. Kaashoek, "A measurement study of available bandwidth estimation tools," in Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference (IMC '03), pp. 39-44, Miami Beach, Fla, USA, October 2003.

[11] L. Angrisani, G. Miele, R. Schiano Lo Moriello, M. Vadursi, "A kalman filtering based method for available bandwidth measurement," in Proceedings of the IEEE International Instrumentation and Measurement Technology Conference (I2MTC '15), pp. 1215-1220, IEEE, Pisa, Italy, May 2015.

[12] December 2015, http://www.idt.mdh.se/~ajn12/index.phtml?choice=software

[13] M. Jain, C. Dovrolis, "End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput," IEEE/ACM Transactions on Networking , vol. 11, no. 4, pp. 537-549, 2003.

[14] S. Suthaharan, S. Kumar, "Measuring available bandwidth: pathChirp's chirp train structure remodeled," in Proceedings of the Australasian Telecommunication Networks and Applications Conference (ATNAC '08), pp. 379-384, Adelaide, Australia, December 2008.

[15] N. Hu, P. Steenkiste, "Evaluation and characterization of available bandwidth probing techniques," IEEE Journal on Selected Areas in Communications , vol. 21, no. 6, pp. 879-894, 2003.

[16] V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, R. Baraniuk, "Multifractal cross-traffic estimation," in Proceedings of the ITC Specialist Seminar on IP Trac Measurement, Modeling, and Management, Monterey, Calif, USA, September 2000.

[17] L. Lao, C. Dovrolis, M. Y. Sanadidi, "The probe gap model can underestimate the available bandwidth of multihop paths," ACM SIGCOMM Computer Communication Review , vol. 36, no. 5, pp. 29-34, 2006.

[18] M. S. Grewal, A. P. Andrews Kalman Filtering. Theory and Practice , Prentice Hall, Englewood Cliffs, NJ, USA, 1993.

[19] G. Welch, G. Bishop An Introduction to the Kalman Filter , University of North Carolina at Chapel Hill Department of Computer Science, Chapel Hill, NC, USA, 2001.