Capacity Estimation, Ensemble Estimation, Testbed, and Network Measurement (Research Paper Sample)

Name

Course
University
Abstract: The end-to-end capacity, defined as the maximal transmission rate of the weakest link on the entire path between two end hosts, plays an important role in efficient network design and management. Although various capacity estimation tools have been proposed in the literature, there is still uncertainty in their accuracy and reliability when they are used in today’s IP-based communication networks. The main reason for this is that all current capacity estimation tools only yield a potential candidate for an acceptable estimate, without being aware of its reliability level. In this study, we propose a new feedback-assisted end-to-end capacity estimation (FACEST) procedure that not only produces a candidate for a potentially acceptable estimate but also improves and categorizes its reliability level. Particularly, FACEST follows an ensemble estimation approach which meaningfully utilizes the correlation among the estimates produced by 3 independent capacity estimation tools; namely pathrate, DietTOPP and PBProbe. Through the correlation of 3 individual estimates, additional information about their reliability level is gained and, if necessary, the experiment is iteratively repeated with different sets of measurement parameter values until the required level of estimation accuracy is achieved, or in the worst case a kernel density estimator is applied on the collected experiment results. The proposed ensemble estimation approach has been implemented in a tool called FACEST, the performance of which has experimentally been evaluated on a three-hop testbed using a variety of tests with several scenarios and degrees of cross-traffic. For comparison purposes, individual experiments with pathrate, DietTOPP and PBProbe as well as with other alternative hybrid estimation tool from literature have also been conducted. The results reveal that FACEST outperforms individual and other hybrid capacity estimation tools and yields up to 18.29% lower estimation errors along with additional consistent information about the reliability level of the produced estimates. Key words: Capacity estimation, ensemble estimation, testbed, network measurement
Introduction
The area of bandwidth estimation research attracts researchers’ attention for many years, and still developing new estimation techniques steadily gains an increasing popularity. In principle, in bandwidth estimation research there exist 3 major metrics: capacity, available bandwidth and throughput. The capacity states the maximum number of bits per time unit a network link can theoretically transfer. The available bandwidth of a network link is defined as the average residual capacity of that link in a given time period. Finally, throughput, in turn, can be categorized in achievable throughput or bulk transfer capacity (BTC). Achievable throughput is the maximum number of bits per time unit that a link can provide to an application, given the current utilization, the transport protocol and operating system used, and the end-host performance capabilities. In contrast to achievable throughput, which can be measured using different transport protocols and multiple parallel connections, BTC is a TCP specific metric exhibiting the maximal throughput attainable by a single TCP connection. Each of these metrics can be estimated either on the entire path between 2 end-hosts (i.e. at the end-to-end scope) or hop-by-hop. For a formal and detailed definition of these metrics, the interested reader is referred to the respective literature [1–3].
Knowledge and monitoring of bandwidth-related metrics are of great interest for both network operators and end-users as they play a significant role in efficient network management and operation. Acquiring information about capacity can e.g. be useful in validating service level agreements, detecting and bypassing bottleneck links, and performing network tomography to track and visualize Internet topologies. Similarly, knowledge and monitoring of available bandwidth and achievable throughput/BTC can help in diagnosing congested or underutilized links, detecting denial of service attacks, applying admission control policies at massively-accessed content servers, and optimizing network route selection and congestion control mechanisms for reliable transport protocols (e.g. for TCP) [4, 5].
Given the variety of bandwidth-related metrics and motivations, a plethora of techniques and tools for estimating the capacity, available bandwidth and achievable throughput/BTC has been developed in the last 2 decades. Figure 1 shows an overview of some major bandwidth estimation techniques and tools. Packet pair and packet train techniques estimate the end-to-end capacity; packet cartouche technique estimates the bottleneck capacity on a subpath segment consisting of a number of consecutive links of an end-to-end path; variable packet size and packet tailgating techniques estimate the per hop capacities; equally spaced mode gaps technique estimates the capacities of multiple congested links along a path; probe gap model and probe rate model estimate the end-to-end available bandwidth; and finally TCP connection and emulation techniques measure the achievable throughput and BTC. Each estimation technique is represented by several various tool implementations. They show a wide spectrum of different characteristics, such as, among other things, whether they perform the measurement actively or passively, their ability to measure asymmetric links, and the type of their deployment, i.e. whether they are run on one or both end hosts of the path under measure.
In contrast to available bandwidth and throughput metrics, the capacity is independent of the current utilization on the measurement path and does not vary over time. The not time-varying property relatively simplifies the estimation of capacity over the other 2 metrics as there is no compelling constraint on measurement duration and overhead. However, despite these beneficial properties and the significant previous research on estimating the end-to-end capacity, up to now we are still rather far from having reliability-aware accurate estimation procedures. The broad survey revealed that the inaccuracies and unreliabilities in estimating the end-to-end capacity are caused by a variety of different challenges/flaw sources that negatively affect the robust working of an estimation procedure. One of the most common reasons leading to inaccurate and unreliable estimates is that real measurement paths always contain cross-traffic which often disturbs the time gaps of carefully scheduled probing packets. To make the estimation tools cross-traffic resistant, several techniques have been proposed including confidence intervals, kernel density estimators and lower/upper bound filtering techniques. Unfortunately, there is no standard statistical approach that always leads to correct capacity estimates. The main reason making the deal with the cross-traffic difficult is that there exist several types of cross-traffic with different behaviors (e.g. deterministic cross-traffic rates, bursty cross-traffic or cross-traffic obeying to a particular distribution like exponential, Poisson or Pareto distribution) that interfere with an estimation procedure in different ways. In addition to cross-traffic induced disturbances, there are also several other challenges such as interrupt coalescing [6], limited system timer resolution [7], route alternations and multichannel links [8], traffic shapers [9] or network components working with non-FIFO queuing disciplines [10],