Knowing the largest rate at which data can be sent on an end-to-end path such that the egress rate is equal to the ingress rate with high probability can be very practical when choosing transmission rates in video streaming or selecting peers in peer-to-peer applications. We introduce probabilistic available bandwidth, which is defined in terms of ingress rates and egress rates of traffic on a path, rather than in terms of capacity and utilization of the constituent links of the path like the standard available bandwidth metric. In this paper, we describe a distributed algorithm, based on a probabilistic graphical model and Bayesian active learning, for simultaneously estimating the probabilistic available bandwidth of multiple paths through a network. Our procedure exploits the fact that each packet train provides information not only about the path it traverses, but also about any path that shares a link with the monitored path. Simulations and PlanetLab experiments indicate that this process can dramatically reduce the number of probes required to generate accurate estimates.
study in more depth the transition point and the relation between the input output ratio and the input rate @cite_0 . They derive a stochastic response curve that is tightly lower bounded by its fluid counterpart (used by previously referenced techniques) and conclude that this transition point is not exact. The idea of stochastic service curves, which expresses the service given to a flow by the network in terms of a probabilistic bound, was also used by to provide bounds on end-to-end delay @cite_3 . In the context of available bandwidth estimation, propose an elegant theoretical framework based on min-plus algebra, but only for worst-case deterministic estimations @cite_12 .
@cite_0 @cite_12 @cite_3
2082841997 2158352245 2140314025 10991463
The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by O(Hlog H), where H is the number of nodes traversed by a flow. Using currently available techniques that compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by O(H3). The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by spl Oscr (H log H), where H is the number of nodes traversed by a flow. Using currently available techniques, which compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by spl Oscr (H sup 3 ). A basic calculus is presented for stochastic service guarantee analysis in communication networks. Central to the calculus are two definitions, maximum-(virtual)-backlog-centric (m. b. c) stochastic arrival curve and stochastic service curve, which respectively generalize arrival curve and service curve in the deterministic network calculus framework. With m. b. c stochastic arrival curve and stochastic service curve, various basic results are derived under the (min, +)algebra for the general case analysis, which are crucial to the development of stochastic network calculus. These results include (i)superposition of flows, (ii)concatenation of servers, (iii) output characterization, (iv)per-flow service under aggregation, and (v)stochastic backlog and delay guarantees. In addition, to perform independent case analysis, stochastic strict server is defined, which uses an ideal service process and an impairment process to characterize a server. The concept of stochastic strict server not only allows us to improve the basic results (i)-(v)under the independent case, but also provides a convenient way to find the stochastic service curve of a serve. Moreover, an approach is introduced to find the m.b.c stochastic arrival curve of a flow and the stochastic service curve of a server. The issue of Quality of Service (QoS) performance analysis in packet switching networks has drawn a lot of attention in the networking community in recent years. There is a lot of work including an elegant theory under the name of network calculus focusing on analysis of deterministic worst case QoS performance bounds. In the meantime, other researchers have studied the stochastic QoS performance for specific schedulers. As yet, there has been no systematic investigation and analysis of end-to-end stochastic QoS performance. On the other hand, most of the previous work on deterministic QoS analysis or stochastic QoS analysis only considered a server which provides deterministic service, i.e. deterministically bounded rate service. Few works have considered the behavior of a stochastic server providing input flows with variable rate service. In this report, we propose a stochastic network calculus to systematically analyze the end-to-end stochastic QoS performance of a system with stochastically bounded input traffic over a series of deterministic and stochastic servers. The proposed framework is also applied to analyze per-flow stochastic QoS performance since a server serving an aggregate of flows can be regarded as a stochastic server for individual flows within the aggregate under aggregate scheduling. Keywords Stochastic Modeling, Network Calculus, Quality of Service