Subject: [ippm] bandwidth measuring/estimating

From: Mark Santcroos <[email-masked]>
Date: Tue, 12 Jun 2001 10:37:13 +0200

Hi,

I am looking into calculating/estimating bandwidth on the Internet.

I know about the BTC framework and the corresponding metric, but that is
not what we are looking for in our project (www.ripe.net/test-traffic/).
The reason for that is that we don't want to regularly fill the line
while doing our measurements.

Better would be something like 'pathchar', described and implemented by
Van Jacobson. (And since then some other implementations)

I'm curious if any effort has been made into standardizing this work.

Also I am wondering if the IPPM would be the right place to discuss this.
Following to that, is the nature of the measurements, based on estimation,
suited for being discussed here and possibly become a standard?

Thanks in advance,

Mark

-- 
Mark Santcroos				RIPE Network Coordination Centre
http://www.ripe.net/home/mark/		New Projects Group/TTM
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: stanislav shalunov <[email-masked]>
Date: 12 Jun 2001 09:59:42 -0400

Mark Santcroos <[email-masked]> writes:

> I know about the BTC framework and the corresponding metric, but
> that is not what we are looking for in our project
> (www.ripe.net/test-traffic/).  The reason for that is that we don't
> want to regularly fill the line while doing our measurements.

Mark,

As far as I understand, the only currently known way to measure link
capacity without filling the link (or asking the router) is to measure
the serialization delay.  Several techniques and programs are
available for this purpose.  If you're only interested in bottleneck
link capacity, you could simply pass back-to-back packet pairs (and
look for spacing on the other end) or packets of different sizes (and
look for difference in transmission time).  If you want to measure
capacities of intermediate links you necessarily have to make the
routers generate some packets (which usually happens in the slow
path).

Any of the techniques works fairly well for low speeds.  For a T1, you
can get a very reliable and precise capacity estimate (even with a
simple tool like bing) unless the link is very heavily overloaded.
However, as the bottleneck link gets faster, it becomes harder to
register tiny serialization delay at all.  To tell an OC-3 from an
OC-12 you need to be able to tell 74us from 18us.  To tell an OC-12
from an OC-48, you'd have to be able to distinguish between 18us and
5us.  Further, this is complicated by the fact that in order to get an
OC-whatever bottleneck you'd have to have very well connected
measurement nodes.  You probably would have to think at least about
timestamping in the driver and Gigabit Ethernet connections...

Note that to measure these high speeds within BTC framework you still
need to overcome significant difficulties (bus bandwidth, etc.).

Good luck,
-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

This message is designed to be viewed at sea level.
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: k claffy <[email-masked]>
Date: Tue, 12 Jun 2001 11:18:50 -0700

margaret did a survey page of these in preparation
for a proposal we wrote to try to work on this topic
(const, downey, mah)
http://www.caida.org/analysis/performance/bandwidth/

bloody hard problem
k

On Tue, Jun 12, 2001 at 10:37:13AM +0200, Mark Santcroos wrote:
  Hi,

  

  
  Thanks in advance,
  
  Mark

---

From: Mark Santcroos <[email-masked]>
Date: Tue, 12 Jun 2001 21:22:36 +0200

Hi Stanislav,

Accurate timekeeping is not a problem for us; Our boxes are equiped with GPS.

While the quality of the method is of course important, an important drive
for us is also that we want to follow standards. (Or develop one)
That way we can make the testbox an implementation independent measurement
device.  (Just as with the OWDP)

As for the bottleneck versus intermediate link capacity: Currently we are
only measuring end-to-end on the Internet. Measuring bottlenecks is
therefor not very useful now.
However, we plan to install testboxes at reference points (IX's for
example), which will make it far more interesting to know bottlenecks
then.

Also, you mention fitting it within the BTC framework, I don't think that
is suited or wanted, do you?

Mark

---

From: Mark Santcroos <[email-masked]>
Date: Tue, 12 Jun 2001 21:25:40 +0200

Hi,

I'm familiar with that section of your website.

What's the status of the proposal and is it public?

Mark

---

From: Constantinos Dovrolis <[email-masked]>
Date: Tue, 12 Jun 2001 18:17:16 -0400 (EDT)

I would also be interested to see some IPPM work in the
direction of bandwidth estimation. A critical point though is
to precisely define what we mean by "bandwidth estimation". I can
see at least 3 different metrics (or types of metrics):

1. Capacity C: the maximum throughput that a certain path can provide,
   in the absence of any competing traffic, and independent of the
   transport protocol or specific application that we use.
   People also refer to this as "raw bandwidth", or "bottleneck
   bandwidth" of the path. This is an important metric mainly
   for network management, debugging, and monitoring. While
   experimenting with pathrate, I found in interesting that network
   managers do not know often the capacity of their links.
   Just because you lease a 40Mbps share of a link, it does
   not mean that the provider will actually give you 40Mbps at all
   times..

2. Available bandwidth A: this is certainly not a consistently
   defined metric in both the research literature and in practice.
   IMHO it should mean: the minimum throughput that is not used
   by existing traffic, across all links of the path. Intuitively,
   in the case of one link, this is just the "blank space" in an MRTG
   graph, between the bandwidth that is currently used and what
   is the capacity of the link. In a multi-hop path, we need
   to know the minimum such "blank space" across all links of
   the path.

   Again, A does not depend on a specific transport protocol.
   Also, it is not true that a single flow would be able to
   achieve A (at least without feedback from the network).
   Depending on how "congestion responsive" the flow is, it may
   get less than A, or more than A.
   From this point of view, A may be a more important metric for
   network monitoring and QoS provisioning, rather than for individual
   users and applications.

3. Bulk-Transfer Capacity BTC: this is the throughput that a
   long TCP connection connection would get from the path,
   if it was only limited by the network (i.e., not limited
   by the advertised window or the amount of data to be sent), and
   if TCP is implemented as in RFC2581. In some sense, this is
   a more pragmatic metric, as it is easier to measure, and
   it is directly related with what most users (at least, TCP
   users that create "elephant" flows) would care about.

Note that each of these metrics is limited by a different part
of the path. The capacity C would be limited by the link
with the lowest capacity (what we call "narrow" link). The
available bandwidth A would be limited by the link with the
minimum unused throughput (what we call "tight" link). The
BTC would probably depend on all the links of the path, since
the throughput of a long TCP connection depends on the end-to-end
loss rate and round-trip time (including queueing delays) that
the connection encounters.

I believe that there are important applications for all these
three types of metrics. So far the focus of the IPPM group
was on the BTC metric. Would there be any interest to consider
the metrics C and A as well? Or any other metrics?

Constantinos

Computer and Information Sciences - University of Delaware

http://www.cis.udel.edu/~dovrolis/

---

From: Mark Santcroos <[email-masked]>
Date: Wed, 13 Jun 2001 08:26:16 +0200

Hi Constantinos,

Actually how different in practice are metric A and C?
I can see the difference in the definition, but in practice it would be
very hard to make a difference between those two probably. (And it may be
a requirement that these are handled the same way)
Please explain me though if you think we should really separate those two.

For now, my requirements for the metric would be:

* transport protocol independent
* path/link usage independent 
* minimal network traffic created by the measurements
* link type independent (if at all possible)

I think these match pretty well with your definitions.

I'm looking forward to your reply.

Mark

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Wed, 13 Jun 2001 17:50:11 +0200 (CEST)

> Actually how different in practice are metric A and C?

Huge, I'd guess: C is a property of the path, independent of the usageof
the path, while A is determined by the path and the usage.

If C is 40 Mbps and there is no traffic along the path, then A will also
be 40 Mbps. However, if some application starts to send 30 Mbps on this
path, then C is still 40 Mbps but A is reduced to 40-30=10 Mbps. 

> > > suited for being discussed here and possibly become a standard?

------------------------------------------------------------------------------
Henk Uijterwaal                    Email: [email-masked]
RIPE Network Coordination Centre     WWW: http://www.ripe.net/home/henk
Singel 258                         Phone: +31.20.5354414
1016 AB Amsterdam                    Fax: +31.20.5354445 
The Netherlands                   Mobile: +31.6.55861746  
------------------------------------------------------------------------------

As long as you don't tell your friends how I played the hand,
then I won't tell my friends how you defended it.                 (Anonymous)

---

From: Jambi Ganbar <[email-masked]>
Date: Wed, 13 Jun 2001 17:05:59 -0400 (EDT)

Const and all,

>    not mean that the provider will actually give you 40Mbps at all

from past work with pathchar I seem to remember that the tool tends to
generates quiet a bit of traffic.  Are there tools that do not utilize the
pipe (or keep utilization to minimal) in order to estimate path b/w?

>    network monitoring and QoS provisioning, rather than for individual

IMOHO this is an important parameter however it is very time dependent and
a function of time should be represented in the definition.  

>    users that create "elephant" flows) would care about.

I'd like to propose that the BTC parameter might be somewhat arcane
enough at this point to elicit some thoughts about a new parameter that is
somewhat reflective of today's traffic patterns. 
from recent discussions (e2e and ippm I believe) and papers on Internet
traffic mix (kc and shawn mccreary) it seems that throughput behavior of
short tcp connections (i.e. http traffic) is something that this group
should be considering.  IMOHO the above mentioned second point can address
such interest as long as we keep in mind "Web time" (rtt/short attention
span).
Any ideas on this?

> the metrics C and A as well? Or any other metrics?

i echo this sentiment and hope that the answer is yes.
Jambi
vBNS+ Engineering.

---

From: Victor Reijs <[email-masked]>
Date: Thu, 14 Jun 2001 10:59:03 +0100

Hello Constantinos,

In my work to try define a end-user QOS metric, I find that the
parameter A is an important one. See also:
http://www.heanet.ie/Heanet/projects/nat_infrastruct/nettools.html

There are a lot of tools for the C measurement, but they are not very
interesting for an end users (it is only a theoretical capacity, which
is never gainable for one user). This tool is of course interesting for
network engineers.

And BTC is of course handy for the TCP users. But how will that change
in the future, with all these UDP based applications? But anyhow BTC is
defined and tools exists, so that is great.

We are trying to stimulate the making a tool A. In that way an end-user
is perhaps able to determine before hand if his/her application can run
over the network.
I would wish that tool A is independent of protocol, but I wonder if
that is possible? UDP can 'make' bandwidth, while FTP has the feedback
(but there the tool for determine available ftp bandwidth is available:
BTC).

Perhaps we should redefine tool A to something like:
'A tool that measures the bandwidth available to an UDP stream without
this stream influencing the existing traffic. The tool must be able to
measure also short term changes' 
The term 'without' is of course something statistically!
'Short term' is another difficult temr: A tool like pathchar can take up
to 15 minutes and 15 minutes is a very long time in IP world;-)

So to end this e-mail, I am very interested in such a tool and its
standard!

All the best,

Victor

> see at least 3 different metrics (or types of metrics):
....

---

From: Constantinos Dovrolis <[email-masked]>
Date: Thu, 14 Jun 2001 09:36:09 -0400 (EDT)

Hey Jambi!

> pipe (or keep utilization to minimal) in order to estimate path b/w?

The capacity estimation tools that I know of are the following. Plz
let me know if there are more out there.

1. pathchar	(Van Jacobson, ftp://ftp.ee.lbl.gov/pathchar/)
2. clink	(Allen Downey, http://rocky.wellesley.edu/downey/clink/)
3. pchar	(Bruce Mah, version 1.4 was just released yesterday,
		see  http://www.employees.org/~bmah/Software/pchar/)
4. pipechar	(Jin Guojun, http://www-didc.lbl.gov/pipechar/)
5. nettimer     (Kevin Lai,
	http://mosquitonet.stanford.edu/~laik/projects/nettimer/)
6. bprobe	(Bob Carter,
		http://cs-people.bu.edu/carter/tools/Tools.html)
7. pathrate	(myself, version 2.0 will be available by the end of June
		at  http://www.cis.udel.edu/~dovrolis/bwmeter.html)

Even though there are several tools available, they are all different in
several aspects. I usually think of bandwidth estimation tools
based on the following questions (in random order):

a) Does this tool attempt to measure capacity, available bandwidth, BTC,
   something else?

b) Does it use information from the routers (i.e., SNMP-based tools like
   MRTG), or is it based on end-point measurements?

c) Does it measure a bandwidth estimate (capacity or available bandwidth)
   for *each link* in the path, or at an *end-to-end* basis?

d) Does it require access at both ends of the path? If not, does it run
   from the sender or the receiver? Can the reverse path affect the
   measurements?

e) Is it based on the dispersion of packet pairs/trains (e.g., bprobe,
   pathrate), on the one-way delay variations of variable-sized
   probing packets (e.g., pathchar, clink, pchar, nettimer, pipechar),
   on actual TCP transfers (e.g., BTC measurements with cap, ttcp,
   iperf), or on emulated TCP flows (TReno)?

f) Does it require ICMP replies from the path routers?

g) Does it attempt to saturate the path over the duration of the
   measurements?

h) Is it portable to different platforms?

i) Does it take user-level or kernel-level timestamps? Timestamping
   accuracy and resolution are MAJOR issues in measuring high-bw paths.
   Resolution is not a problem these days (1-2usec is typical). Accuracy,
   though, can be a major problem in both kernel and user-level
   timestamps (more in the later), and especially when the measuring host
   is not totally idle.

j) In the case of a capacity-measuring tools, is it robust to cross traffic?
   In other words, can it make accurate measurements even when the path
   is heavily loaded?

k) Are the measurements affected by "hidden" L2 switches and other
   store-and-forward devices?

l) Can it measure the aggregate capacity of parallel-links?

m) Does it require access at the raw-IP socket (i.e., need special
   user privileges)?

n) Probably the most important issue: Is it accurate? Obviously, all
   these tools are based on statistical methodologies. This means that
   there is no guarantee that they will give you the right value everytime
   you run them. The possibility of error is always there in every
   area of measurements and experimentation. However, do they give the
   right estimate "most of the time"?

Ok, I almost run out of letters here.. Any other important issues that
we should consider in such a classification?

Constantinos

---

From: Constantinos Dovrolis <[email-masked]>
Date: Thu, 14 Jun 2001 10:01:20 -0400 (EDT)

Mark, as Henk pointed out A and C are generally very different.
If you are interested in something that is "usage independent",
you probably refer to a capacity metric. What do you mean
"link type independent"?

Cheers

Constantinos

---

From: Victor Reijs <[email-masked]>
Date: Thu, 14 Jun 2001 15:13:18 +0100

Hello all of you,

>                 http://cs-people.bu.edu/carter/tools/Tools.html)

cprobe (I think of the same author). Could measure bandwidth A.
http://cs-people.bu.edu/carter/Papers.html

>                 at  http://www.cis.udel.edu/~dovrolis/bwmeter.html)

8. Reading MIB's (as you point out later in b).

>    from the sender or the receiver? Can the reverse path affect the

Related to this one, but could open the idea of a 'testing protocol':
Can it handle downloads of script to perform different test dynamically?
Anoteh related one:
Can one start up the test remotely on one of the end-points (and not
being logon in an endpoint)? Pehaps using SSL?

>    right estimate "most of the time"?

Perhaps I would rephrase it a little bit: Is it accurate enough? Every
application of such a tool could need a different level of accuracy and
perhaps a simpler tool coudl be used for certain tasks.

> we should consider in such a classification?

VERY GOOD Overview!!!!

All the best,

Victor

---

From: Mark Santcroos <[email-masked]>
Date: Thu, 14 Jun 2001 16:15:30 +0200

Hi Constantinos,

> you probably refer to a capacity metric. What do you mean

I agree that they are not the same ;) I was unclear/incorrect in my
explanation.

I think I was indeed referring to something you call a 'capacity metric'.

However, it is not yet clear to me what I want to establish exactly;
Probably we just want to find out both. I first saw them as one, but it is
clear to me know that they are two totally different things.

To answer your last question: it would be nice to come up with a method
that is independent of underlying layers on the network. So try to stay free
of L2 tricks as much as possible. I have no idea how realistic this wish
is though.

Mark

---

From: Constantinos Dovrolis <[email-masked]>
Date: Thu, 14 Jun 2001 19:38:13 -0400 (EDT)

> http://cs-people.bu.edu/carter/Papers.html

Victor,

What cprobe measures is an interesting issue. cprobe sends several,
say N, back-to-back packets (a "packet train") from the source of the
path to the sink. Based on the overall "dispersion" of the train at
the receiver, say Delta, it computes a bandwidth estimate:
	b = (N-1) L / Delta
where L is the size of each packet in the train. In the case of cprobe,
N is 8 packets I think.

In a recent work that we did with the Caida folks, (published at last
Infocom, see http://www.cis.udel.edu/~dovrolis/Papers/infocom01.ps) we
showed that the dispersion of long packet trains is *not* related with the
available bandwidth in the path. The bandwidth estimates, instead,
become centered around a certain value that we call "Asymptotic
Dispersion Rate" (ADR). The ADR is a function of the capacities
and loads of all the links in the path (in the general case).

In the case of a single-link path, we can compute the available bandwidth
A from the measured ADR, but that is a very limited case of course.

To make the long story short, I don't know of any end-to-end tool
at this point that can measure the available bandwidth in a path.

Cheers

Constantinos

---

From: k claffy <[email-masked]>
Date: Sat, 16 Jun 2001 00:35:29 -0700

On Thu, Jun 14, 2001 at 09:36:09AM -0400, Constantinos Dovrolis wrote:
  
  Hey Jambi!

not only that, but which ones actual
ISPs want us to pursue use of;
the more ISPs on board w us
(in terms of providing  calibrating link.bandwidths)

k

  

  

  

  

  

  Constantinos

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Mon, 18 Jun 2001 16:26:17 +0200 (CEST)

Constantinos,

Great list, I think that trying to answer them for all tools is going to
be very helpful.

A few small additions.

> g) Does it attempt to saturate the path over the duration of the

I think we have to quantify this, for operational use, a tool that
saturates a link for a short time, is fine, a tool that saturates it for
hours isn't. 

And for the tools that don't saturate, it could still be useful to have
an idea about the data volume to be sent out.

> h) Is it portable to different platforms?

I guess you mean: "on which platforms does it run?"

>    right estimate "most of the time"?

n1) Does it calculate (correct) experimental errors?

o) Is the tool actively maintained/developped?

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Mon, 18 Jun 2001 16:33:37 +0200 (CEST)

Matt,

It appears that the IPPM archive
(http://www.advanced.org/IPPM/archive/date.html) ends on April 5.  Would
it be possible to include later postings to the list?

Henk

---

From: Constantinos Dovrolis <[email-masked]>
Date: Wed, 20 Jun 2001 08:39:31 -0400 (EDT)

Hi Henk,

> saturates a link for a short time, is fine, a tool that saturates it for

It would be useful to hear more from operations people about what
timescales are acceptable for saturating a path. A train of 20
back-to-back 1500-byte packets saturates a fast ethernet for about
2.5msec. Obviously not many people would care. On the other hand, a tool
that attempts to saturate the path for several minutes with TCP traffic,
or even worse with a UDP flow, would cause noticeable effects on the rest
of the traffic. What about the large grey zone between a few
msec and several minutes?

> I guess you mean: "on which platforms does it run?"

Correct.

> n1) Does it calculate (correct) experimental errors?

Well, none of the tools that I know of provide some degree of confidence
on the final capacity estimates. It is an interesting next-step to look at.

> o) Is the tool actively maintained/developped?

Very important. AFAIK, the capacity estimation tools that are actively
maintained at this point are pchar, clink, pipechar, nettimer, and
pathrate.

Constantinos

---

From: Jambi Ganbar <[email-masked]>
Date: Thu, 21 Jun 2001 12:03:49 -0400 (EDT)

Sorry for taking a while to answer.
If I man be the voice of this operational network (i.e. vbns)

> msec and several minutes?

The answer really depends on the network and on what you are trying to
test.

1.  The premise of this thread if I remember correctly was a statement made
wrt "I'm surprised more people are not interested in validating what their
b/w is from their provider."  In that case where Joe pays for a 40Mb/s
pipe to his provider and Joe wants to check that her provider really gives
her the b/w she cares to pay for the test is really only hurting Joe if
Joe decides to saturate a link for a long period of time.
If Joe targets the provider's router though Joe is likely to have some
very upset provider at the other end of the phone.  Routers are not good
targets for such tools as they should be routing not measuring.

2.  end to end path.  In this scenario we are trying to test a path that
goes from one end on the network (you) to another end (them).  It could
potentially traverse several networks with varying degrees of congestion.
This is something that I think about two ways:
high packet rate/large packets traffic could look very similar to bulk
transfer rate.  So if Joe wants to grab that 10MB mp3 file from a host
across the network joe will be generating high packet rate traffic.  
BUT If my tool is trying to estimate path b/w my tool will be taking away
from legitimate users b/w by generating traffic to measure the link.
  Short bursts (ms time frame) are in the noise most of the time unless
your links are really THAT congested and your buffers and stressed as it
is.

I'd love to know what other ippmers think
jambi

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Fri, 22 Jun 2001 16:46:27 +0200 (CEST)

> on the final capacity estimates. It is an interesting next-step to look at.

In first order, I'd think that this is very simple to calculate: all
programs measure RTT as a function of number of bytes sent, then determine
the slope of this line by fitting it to a straight line, the bandwidth is
then 1/slope (Byte/sec).   All fitting methods can also give error
estimates on the slope and this can be easily turned into an experimental
error on the bandwidth.

Since this is all very simple, I'm surprised that none of the tools do
this, can anybody explain why or did I overlook something?

Henk

---

From: [email-masked] (Bruce A. Mah)
Date: Fri, 22 Jun 2001 07:55:28 -0700

> estimates on the slope and this can be easily turned into an experimental

Followed you all the way up until the last sentence.  Is there an easy 
way to do this part?

> this, can anybody explain why or did I overlook something?

Errr...pchar does, depending on which linear fit you tell it to 
use.  For the least sum of squares and least median of squares fits, it 
gives the coeffecient of determination.  For the non-parametric, 
rank-based fit, it gives a confidence interval for the slope.

Also, the pathchar/clink/pchar family of programs relies on 
differencing between adjacent partial paths to compute per-link 
estimates; it wasn't clear to me how to do a confidence interval or 
other goodness-of-fit parameter for the per-link parameters (after the 
differencing).  So it's not quite as easy as you made it sound.....

Bruce.