端到端估计网络路径带宽变化范围的非参数与参数方法

需积分: 49 177 浏览量更新于2024-09-10 收藏 262KB PDF 举报

本文主要探讨了网络路径可用带宽（Available Bandwidth, avil-bw）估计中的一个关键问题——端到端的可变范围（End-to-end Variation Range）。在现代网络中，可用带宽作为衡量性能的重要指标，其变化性在不同时间尺度下尤其显著，然而过去的许多研究主要关注于平均带宽的估算，而忽视了这一特性对网络性能理解的重要性。论文提出了一种新的方法，旨在解决如何在用户指定的时间尺度上准确地估计某个百分位的可用带宽分布。作者认为，如果能够获取分布的两个关键百分位（如10%到90%），就能得到一个实用的带宽变化范围的估计。这种估计方法分为两种： 1. 非参数迭代法：这种方法适用于极短的时间尺度（通常小于100毫秒）以及带宽分配有限的瓶颈区域，比如当网络流量多且竞争激烈时，可用带宽的分布可能偏离正态分布，此时非参数估计更为合适。通过迭代过程，这种方法能够更精确地捕捉到实时变化的带宽情况。 2. 参数化方法：这种方法基于可用带宽遵循高斯分布的假设，通过更快的计算速度提供估算。尽管对于某些稳定条件下的网络环境，高斯分布假设可能是合理的，但在复杂网络环境下，这种假设可能并不总是适用。为了实现这些技术，作者们开发了一个名为Pathvar的测量工具。Pathvar能够在各种非稳态条件下，准确跟踪并估算可用带宽的变化范围，误差控制在10%-20%之间。此外，论文还深入分析了影响可用带宽变化范围的四个关键因素：交通负荷、竞争流的数量、竞争流的速度，以及测量的时间尺度。这些因素相互作用，共同决定了网络性能的动态变化，因此在进行带宽估计时必须予以考虑。本文的研究对于网络设计者和优化者来说具有重要意义，它提供了一种有效的方法来理解和预测网络可用带宽的不稳定性，这对于实时网络管理和性能优化至关重要。同时，它也提醒我们在评估网络性能时，不能仅仅依赖平均值，而是需要充分考虑其波动性和潜在的不确定性。

eling and analysis, and in particular, the measurement of

the second-order statistics (variance and autocorrelation) in

various time scales using packet traces. That area, which

started with the seminal Bellcore work [9], revealed that

the traﬃc count process at a network link is asymptotically

self-similar. The reader is referred to [12] for a survey of the

related literature. Our approach and objectives in this work

are signiﬁcantly diﬀerent. First, instead of passive traﬃc

measurements at a single link we are interested in the active

estimation of the avail-bw in an end-to-end path. Second,

instead of focusing on the scaling properties of the avail-bw

process, we focus on the variability of the marginal distri-

bution at a given time scale. Third, our high-level goal is

to develop tools that can be used in practice to measure

important path characteristics, rather than to statistically

characterize or model network traﬃc.

1.3 Main Contributions and Overview

In this paper, we ﬁrst present a measurement technique,

referred to as percentile sampling, that can associate a given

probing rate with a percentile of the avail-bw distribution.

We then use percentile sampling to design two estimation

algorithms for the avail-bw variation range.

The ﬁrst algorithm is iterative in nature. We refer to it as

non-parametric, because it does not assume a speciﬁc avail-

bw distribution. The non-parametric algorithm is more ap-

propriate for very short values of the measurement time scale

(typically less than 100msec) or in bottlenecks with limited

ﬂow multiplexing, where the avail-bw distribution may be

non-Gaussian.

The second algorithm is parametric, because it assumes

that the avail-bw follows the Gaussian distribution. This as-

sumption is typically valid when τ >100-200msec and when

the tight link carries a signiﬁcant amount of aggregated traf-

ﬁc [8]. The parametric algorithm can produce an estimate

faster than the non-parametric algorithm because it is not

iterative.

The two estimation algorithms have been implemented

in a measurement tool called Pathvar. We have validated

Pathvar with simulations and testbed experiments using re-

alistic Internet traﬃc. Pathvar can track the actual avail-bw

variation range within 10-20%, even under non-stationary

conditions.

Finally, we focus on four factors that can signiﬁcantly af-

fect the variation range of the avail-bw. These factors are

the traﬃc load, number of competing ﬂows, rate of com-

peting ﬂows, as well as the measurement time scale. The

results of that study explain why the avail-bw appears as

less or more variable depending on the load conditions and

the degree of statistical multiplexing at the tight link.

The rest of the paper is structured as follows. The per-

centile sampling technique is described in §2. §3 presents the

non-parametric estimation algorithm, while §4 presents the

parametric algorithm. The implementation of Pathvar, and

a few typical validation results, are summarized in §5. Fi-

nally, we examine the four factors that aﬀect the variability

of the avail-bw process in §6. We conclude in §7.

2. PERCENTILE SAMPLING

In this section, we ﬁrst describe the basic technique of

percentile sampling, which forms the basis of the proposed

estimation algorithms in the next two sections. A number

N of probing streams of duration τ and rate R are sent to

a path. Each stream provides an indication of whether the

avail-bw in the corresponding time interval is higher than

R. The resulting N binary samples are used to estimate the

percentile of the avail-bw distribution that corresponds to

rate R. We also derive the required number of samples N

for a given maximum error, assuming independent sampling.

2.1 Basic idea

Consider a network path. The avail-bw random process

measured in time scale τ is A

(t). As mentioned in the Intro-

duction, we assume that this process is stationary and iden-

tically distributed. Given the previous assumptions, we can

focus on the random variable A

and on its time-invariant

marginal distribution F

The sender transmits a probing packet stream of rate R

and duration τ during (t, t + τ) to the receiver. If M is the

packet size, then the interarrival between successive pack-

ets is M/R and the number of probing packets is d

τ R

The avail-bw during (t, t + τ) is given by a realization of

the random variable A

. The receiver classiﬁes the stream

as type-G if it infers that the probing rate R is greater (or

equal) than A

. Otherwise, the stream is classiﬁed as type-

L (for “lower”). The exact algorithm for the classiﬁcation

of a stream as type-G or type-L is described in the techni-

cal report [7]. At a high level, the algorithm is based on

the statistical analysis of the one-way delays of the stream’s

probing packet, similar to the approach taken in [5].

We use the indicator variable I(R) to represent whether

a stream is of type-G (I(R) = 1) or type-L (I(R) = 0). If

(a) is the Cumulative Distribution Function (CDF) of A

we have that

I(R) =



1 with probability F

(R)

0 with probability 1 − F

(R)

So, the expected value of I(R) is E[I(R)] = F

(R).

A single probing stream can only tell us if the probing

rate R is greater than the realization of the avail-bw random

variable in the corresponding time interval. To accumulate

N such samples, the sender transmits N identical probing

streams

. The indicator variable for each stream is denoted

by I

(R). Because diﬀerent streams will sample diﬀerent

realizations of A

, some streams may be classiﬁed as type-G

and others as type-L. Let I(R, N) be the number of streams

of type-G, i.e., I(R, N ) =

i=1

(R). The expected value

of I(R, N) is

E[I(R, N)] =

i=1

E[I

(R)]

= F

(R)N (4)

The following proposition summarizes the basic idea of

percentile sampling:

Proposition 1. For a stationary avail-bw process, the

fraction I(R, N)/N of type-G probing streams of rate R is

an unbiased estimator of p = F

(R).

Proposition 1 provides us with a mapping from a given

probing rate R to the corresponding cumulative probability

in the avail-bw distribution. Since our goal is to estimate

The time period between streams should be suﬃciently

long for the streams to not get queued behind each other

while in transit.

剩余11页未读，继续阅读

Hearthougan

粉丝: 731
资源: 73

端到端估计网络路径带宽变化范围的非参数与参数方法

3D-LaneNet- End-to-End 3D Multiple Lane Detection.pdf

Real-time Mesh-based Scene Estimation

On the Estimation of the Coefficient of Variation for Anisotropic Diffusion

few-shot object detection and viewpoint estimation for objects in the wild

Attentional 2D-Human Pose Estimation

mpi inf 3dhp

lightweight-human-pose-estimation.pytorch-master

详细解释一下FastNet: Fast high-resolution network for human pose estimation

coherent signal-subspace processing for the detection and estimation of angl

最新资源