** Unofficial Release **
			Bing 1.1.2


Table of Contents
-----------------

1. What is bing ?
2. Infos on bing
3. Installing bing
   1. Installing bing on Unix systems
   2. Installing bing on Windows systems
4. How to use bing
5. Measurement problems
6. Packet loss evaluation
7. Ethernet devices measurement
8. Possible NTP influence
9. Possible enhancements
10. Some maths
   1. What is a RTT made of ?
   2. Minimising errors
   3. The linear regression
   4. Measuring asymetric links
11. References


1. What is bing ?
-----------------

Bing is a point-to-point bandwidth measurement tool (hence the
'b'), based on ping.

Bing determines the real (raw, as opposed to available or average)
throughput on a link by measuring ICMP echo requests roundtrip times
for different packet sizes for each end of the link.

Suppose we are on host A and want to know the throughput between
L1 and L2, two extremities of a point-to-point link.

	A ----( the Internet )--- L1 --- L2

If we know the rtt (roundtrip time) between A and L1, and the rtt
between A and L2, we can deduce the rtt between L1 and L2.

If we do that for two different packet sizes, we can compute the
raw capacity (bps) of the link.

Note that bing can also be used to have an idea of ethernet cards
performance.

Many thanks to the following people for their help, hints, support,
and real beers :

	Marc Baudoin		<babafou@ensta.fr>
	Franois Berjon		<fcb@gwynedd.frmug.fr.net>
	Julien Boissinot	<jb@spia.freenix.fr>
	Stphane Bortzmeyer	<bortzmeyer@cnam.fr>
	Jacques Caron		<jcaron@pressimage.net>
	Laurent Chemla		<laurent@brasil.frmug.fr.net>
	Ren Cougnenc		<rene@renux.frmug.fr.net>
	Nat Makarevitch		<nat@nataa.frmug.fr.net>
	Jean-Philippe Nicaise	<nicky@fdn.fr>
	Christian Perrier	<perrier@onera.fr>
	Bertrand Petit		<elrond@imladris.frmug.fr.net>
	Philippe Regnauld	<regnauld@tetard.freenix.fr>
	Ollivier Robert		<roberto@keltia.freenix.fr>
	Herv Schauer		<herve@hsc.fr.net>
	Christophe Wolfhugel	<wolf@pasteur.fr>

Send virtual beers, bug reports, enhancements and flames to :

	Pierre Beyssac		<pb@fasterix.freenix.fr>

2. Infos on bing
----------------

You can subscribe to the "bing-users" mailing list by sending a
mail containing :

	subscribe bing-users

to <majordomo@lists.fdn.fr>.

The posting address is <bing-users@lists.fdn.fr>

3. Installing bing
------------------

The provided source should compile and run out of the box on :

	FreeBSD 1.1.5.1
	FreeBSD 2.0.5
	Linux
	NetBSD 1.0
	SunOS 4.1.3
	AIX
	HP-UX 9
	Solaris 2
	BSDI 1.0
	Ultrix (DECstation)
	Windows 95
	Windows NT 3.51 and 4.0 on i386 (alpha, mips, ppc)

3.1. Installing bing on Unix systems
------------------------------------

On Solaris 2, you should only need to uncomment the CLIBS line
in the Makefile.

Then (on all systems) :
	$ make
	$ su root
	# make install

bing, like ping, needs to be installed setuid root to be able to
make its own ICMP packets.

Note that, to format the man page (bing.8), you'll need the 'mandoc'
macros package. If you don't have it, a preformatted cat page
(bing.0) and postscript page (bing.ps) are provided.

3.2. Installing bing on Windows systems
---------------------------------------

To compile bing you must also get the icmp package. This is a 
package which provides the required include files and libraries 
to send and receive ICMP messages.

To compile bing you may have to modify the file makefile.nt so 
that ICMP_LIBRARY points to the place where you have put the icmp
libraries.
Then the command below should suffice:
	nmake -f makefile.nt

There are options you may add to this command line to customise the result. 
All options are disabled by default:
  - DLL=1
    Links bing with the Dll C library rather. This makes bing much smaller 
    but may require that you ship the Dll with it.

  - DEBUG=1
    Builds a debug version.

  - BROWSER=1
    Generates Visual C++'s "browser" database.

and commands
  - all or <nothing>
    Builds bing.

  - clean
    Removes the generated files.

4. How to use bing
------------------

	1) using 'traceroute', find the IP adresses of the endpoints
	   of the link you want to measure.

	2) try :

		bing -v point1 point2

	   where 'point1' is the nearest endpoint.
	   Option '-v' is useful to be warned of any routing problems.

	3) wait a little for the measure to stabilize.

	4) if after a while, the measurement looks weird (typically,
	   negative or amazing throughputs) have a look at the indicated
	   roundtrip times. If they are too small (below a few milliseconds),
	   try to rerun bing with a bigger packet size :

		bing -S 1000 -v point1 point2

	   CAUTION : do not increase packet size too much, because this
		     could trigger IP fragmentation/reassembly on
		     the link to measure *or* on intermediate links,
		     which messes up the measures completely.

		     If you stay below 1400 bytes, you should be safe
		     (except on SLIP links where you should not go over
		     1000). This depends on the MTU (maximum transmit unit)
		     of the link.

	5) if, after increasing packet size, you still can't get stable
	   results, try to use the -z option. This option fills packets
	   will random data, defeating compressed links.

	6) if you still can't get anything reasonnable, the link you're
	   trying to measure is probably a high-throughput link too far
	   away (network- and throughput-wise) from you, or some weird
	   animal (IP over X25, Frame Relay, ATM, satellite...).

	   You can try to run bing from a better connected machine
	   (with respect to the target link). If you can't, you
	   can always try to think of a way (I'm sure there are)
	   of improving bing to make it work anyway :-).

	   Probably the best solution is to find something else to
	   do (I leave it to your choice entirely, suggestions are :
	   go for a walk, eat, drink, be elected).

5. Measurement problems
-----------------------

There are many cases in which the measurements may not be accurate
(read:  "plain wrong") :

	- links attained through a link of much lower throughput
	  (typically, don't expect to measure a 34Mbps backbone
	  link through your V32bis dialup account). You can
	  expect to measure links about 15 to 30 times faster than
	  the slower link in your path to them, i.e. up to 512kbps
	  through a V32bis modem, up to 2Mbps through a 64kbps
	  link, and so on.

	- saturated links. bing works by measuring the minimal rtts.
	  The more saturated links there are in the measure path,
	  the more time it takes to get a packet through all of
	  them with minimal delay.

	- IP/X25 connections. Due to encapsulation in small packets,
	  it is very difficult to know the "raw" bit capacity
	  because the overhead by IP packet is not fixed and varies
	  with the packet size. However, a clever bing could be
	  able to find out about the encapsulating size by slowly
	  increasing the strobe packet size and detecting steps in
	  the rtt increase.  Maybe one day ;-)

	- more generally, what you might call "hidden multi-hop" links can
	  give strange results. This includes IP over X25, Frame Relay,
	  as well as probably any IP encapsulation over a switched
	  packet network.

	- padding. On many links, the smallest packet size is bigger than
	  the smallest possible IP packet size and padding occurs. For
	  example it happens on ethernet. It tends to give optimistic
	  results.

	- non symmetrical routing : 

		     -----------------<---
		     |			 |
		     |			( somewhere )
		     |			 ^
		     |			 |
	A ---( the Internet )--> L1 ---> L2

	  If the routings are set in such a way that the ICMP echo
	  replies from L2 don't cross the L1-L2 link, bing can't
	  reliably compute the link capacity.

	  It generally happens, at least in France, on links crossing
	  ASs (autonomous systems) between different providers.
	  Sadly, these links happen to be the most interesting to
	  measure, to be able to check providers claims regarding
	  their connection with the rest of the world...

	  I don't think there's an easy way around (this is the
	  same problem as traceroute not being able to report
	  network return paths).

I have been objected that high-bandwidth links with dedicated
routers might be impossible to measure, due to the way these devices
work.

Fast routers are designed in such a way that, when receiving a
packet, they decode the header as soon as possible, even before
the packet is completely received. They can thus decide on an
outgoing route for the packet and might even (I'm not sure about
that) begin resending it before receiving it completely.

This should not directly interfere with ICMP ECHO_REQUEST packets
because these packets must be locally processed and this is generally
done entirely by software at a lower priority when the packet has
been completely received.

Moreover, since bing only considers minimal round-trip times in
its throughput calculations, you only have to expect that some ICMP
ECHO_REQUESTs will be processed by the router as soon as they are
received, which should happen often enough if the router is not
saturated.

6. Packet loss evaluation
-------------------------

Knowing the packet losses on A-L1 and on A-L2, it should be possible
to compute the loss between L1 and L2 :

	A --- L1 --- L2
	   a      b

	A-L1 packet loss = a
	A-L2 packet loss = ab
	L1-L2 packet loss = ab / a

Bing attempts to calculate it, but the results are generally not significant.

7. Ethernet devices measurement
-------------------------------

This might sound surprising, since ethernet throughput is known to
be 10Mbps !

By running bing between two machines on an ethernet, you can evaluate
the CPU overhead induced by memory copies and polled I/O.

For example, between two Sparc 2 running SunOS 4.1.3, I generally
get around 9Mbps. Between two PCs running FreeBSD with NE2000
clones, expect around 4 or 5Mbps (or a little more depending on
processor speed). Between two PCs with 3C509 cards, I get about
7Mbps.

8. Possible NTP influence
-------------------------

Though I never got any evidence of it, it is possible that running
bing on a NTP-synchronized machine introduces a bias in the
measurements, when the NTP daemon makes a small correction while
bing is waiting for an echo reply packet (almost all the time).

I suppose this should mainly have an effect when measuring fast
and far away links, which are difficult or impossible to measure
anyway.

9. Possible enhancements
------------------------

 * It should be possible to measure mono-directional throughput by
varying the packet size only for one of the packets, the sent packet or
the received packet.

For example, sending variable-sized ICMP ECHO_REPLY packets with a 
small TTL should elicit fixed-size "ttl exceeded" replies.

 * Another interesting extension would be a mechanism trying to
determine the optimal big packet size in such a way that the
measurement is accurate enough yet fast.

 * Bing derives from ping and it shows. Its structure could probably be 
enhanced, modularised and simplified. Also many options that were 
significant for ping are not significant for bing and could be removed.

 * Most of the IP options are not supported by the icmp part of the 
Win32 version. While they may not really be needed it they could be 
by building the IP options by hand.

 * On the Win32 version the rtt resolution is only of a millisecond. It
would be nice to find a solution for having a higher resolution.

 * The Win32 error reporting needs to be fixed. It reflects more what
could have happened on Unix that what actually happened and the error
codes are usually incorrect.

 * The makefile is probably too Visual C++ centric. I'd be interested in a 

10. Some maths
--------------

10.1. What is a RTT made of ?
-----------------------------

Sending a packet from host 1 to host 2 involves pushing data through many 
layers: your software and the OS network software, the network device then
the link then up the layers on host 2. The following figure describes this.

                 Host 1            Link             Host 2

          Software    Device                  Device    Software
	|---->-----|---->-----|-->--//-->--|---->-----|---->-----|
                                                                 |
	|----<-----|----<-----|--<--//--<--|----<-----|----<-----|


Each of these layers introduces its own delay which depends on the packet 
size. To model the RTT we will assume that:
* each layer introduces a delay which is a linear function of the packet 
size.
* there is no packet queue. This is only realistic on unloaded networks.

Thus:
Rtt=A1_se+A1_de+A_le+A2_dr+A2_sr + (B1_se+B1_de+B_le+B2_dr+B2_sr) * Se +
    A2_se+A2_de+A_lr+A1_dr+A1_sr + (B2_se+B2_de+B_le+B1_dr+B1_sr) * Sr

where:
* Se is the emmitted packet size and Sr is the returned packet size
* the delay introduced by the software on host 1 when emitting is
  A1_se + B1_se * Se
* the delay introduced by the device in the same situation is
  A1_de + B1_de * Se
* the delay introduced by the link in the same situation is
  A_le + B_le * Se

where in Ah_ld and Bh_ld
 h is the host
 l the layer: software, device or link
 d is the direction: emmision or reception

As you can see this gets quite complex. Does it need to ?
* we would like the delay introduced by the software and the device to be 
negligible. Unfortunately this is not the case. Even when pinging the local
host (the device should not even be used) the Rtt can be up to 1ms on slow 
hosts.

* A1_le and A1_lr represent the time it takes for the signal to proagate 
from host 1 to host 2. This depends on the distance between the hosts and 
the speed of the signal (usually a fraction of the speed of light). This 
should be negligible in lans but certainly is not in satellite or 
transatlantic links.

* At the device level the parameters are certainly the same when sending 
and when receiving a message. At the software level this is probably no 
longuer true since the treatment is not the same. Also it is probably 
difficult to define at which point the message turns around. Finally some 
links are asymetric. Examples of asymetric links include 56K modems, future
ADSL links. Internet connections that involve a satellite as the return 
path do not really enter in this category since they rather involve a 
routing problem.

When we do the difference of the RTT for two different sizes of packets 
what we get is not the intrisic link RAW capacity. This is clear from the 
following formula:

With a fixed Sr:
Rtt_b-Rtt_s = (B1e+Ble+B2r) * (Seb-Ses)

With Se=Sr

Rtt_b-Rtt-s = (B1e+B1r+Ble+Blr+B2e+B2r) * (Seb-Ses)

10.2. Minimising errors
-----------------------

10.3. The linear regression
---------------------------

10.4. Measuring asymetric links
-------------------------------

To measure the bandwidth of asymetric links we should:

First measure the uplink badnwidth

Rtt1_b-Rtt1_s = (B1e+Ble+B2r) * (Seb-Ses)
=> We know B1e+Ble+B2r = (Rtt1_b-Rtt1_s) / (Seb-Ses)

Rtt2_b-Rtt2_s = (B1e+B1r+Ble+Blr+B2e+B2r) * (Seb-Ses)
=> B1r+Blr+B2e = (Rtt2_b-Rtt2_s+Rtt1_b-Rtt1_s) / (Seb-Ses)

11. References
--------------

* Van Jacobson has done some work on network bandwidth measurements. he has 
written a paper on this subject and a tool similar to bing: pathchar. You
will find both at the following address ftp://ftp.ee.lbl.gov/pathchar. 
msri-talk.ps.gz	is a postscript version of his talk at MSRI on bandwidth 
measurement. The pathchar-* files are the binaries of the pathchar tool.

* Stephane Bortzmeyer has written echoping.