If that probability is the same for all intermediate hosts (or can be bounded between a min and a max) we get:

What this tells us is that the probability that the packet is not delayed decreases exponentially with the number of hosts. But note that this does not necessarily mean that we cannot measure far away links. You will probably be able to measure a modem link which is many hops away because the delays will probably be small compared to the rtt difference at the two ends of this modem link. But it does put a limit on our chances to get a good measurement of relatively fast and far away links.

5.9. routers, hubs, switches,..

5.10. things that don't work

aggregated pipes: shotgun modems ?, modem aggregation, aggregated fast-ethernet to a switch

determining half-duplex/full duplex

fixed bandwidth may be wrong for modems

fixed latency may be wrong for satellite links

6. The maths and physics being Bing

This section describes how Bing computes the link characteristics such as the bandwidth. It first describes how we modelize the network (the phiysics), then the algorithms (the maths) and then gives a word of caution about how to interpret the results and why the assumptions we have made may be wrong.

6.1. Network link modelisation

Bing attempts to determine the characterics of the the links that connect TCP/IP hosts. That these links be point to point links or buses does not matter. What is important is that each network link forms a direct connection between the two (or more) hosts, i.e. the TCP/IP packets are not stored and forwarded at any point between the two hosts.

So for instance the in the figure below A-B is a network link but not A-C. This is because a hub does not store and forward IP packets, it starts retransmitting IP packets from the segment 1 to the segment 2 as soon as the first byte is received (in fact it operates at the physical level and does not even know what a byte is). So between A and B a TCP/IP packet is never stored and then forwarded. In contrast the router has to first receive the full TCP/IP packet from segment 2 before it can before it can retransmit it on the segment 3. So by the definition above A-C and B-C are not network links.

       Ethernet        Ethernet           Ethernet
       Segment 1       Segment 2          Segment 3
    A ----------- Hub -----+----- Router ----------- C
                           |
                           B

When we attempt to characterize a network link we will be at one end of it. We will then say that packets leaving our computer are going "up" while packets comming to our computer are going "down" (which keeps with the tradition of uploads and downloads). Each network link can then be split in two: an "uplink" and a "downlink".

Of course in some cases the uplink and downlink are in fact exactly the same link, this is the case in particular of ethernet over a coaxial cable. In other cases they may have the same characteristics, this is the case for instance of ethernet over an RJ45 conenction. But there are also a number of situations where the uplink and the downlink have different characteristics, examples are given in a later section.

Then we characterize each half of the link by the following properties:

• b: the link bandwidth, i.e. the number of bytes that can be transmitted per second. This bandwidth is assumed to be constant in time (at least while we are making our measurement) and independent from the amount of data sent, from the nature of the data sent and from the number of packets sent.
• l: the link latency, i.e. a delay that is incurred every time that data is sent from one end of the link to the other. We assume that this delay is constant in time (again, at least while we are making our measures) and independent from the amount of data sent.

It follows that the time t it takes to send s bytes (in s we include all the protocal overhead) from one host on the link to the other is:

Determining the characteristics of such a network link is then equivalent to determining the values of b and l.

(!!)From there is is trivial to generalize the foNow generalizing the formula above from just one network link to a chain of n+1 hosts (h₀..h_n) connected via n network linksthe round-trip-time will be of the form:

where b_u,i and l_u,i are respectively the bandwidth and the latency of the uplink connecting the host i-1 to the host i and b_d,i and l_d,i are respectively the bandwidth and the latency of the downlink connecting the host i to the host i-1.

Finally we can derive from expression (2) that the round-trip-time is an affine function of the packet size, that is, it is of the form:

where a and b are constants determined by the bandwidth and latency of the intervening network links.

6.2. Intrisic limits and validity of this modelisation

Before we go on to see how we are going to measure the network link's bandwidth let's review the assumptions made by the network link modelisation.

We assume the bandwidth is constant in time. This is not always the case. For instance modems using protocols like V34 or V90 constantly monitor the line quality and adjust their bit rate accordingly. Comes a storm and the bandwidth falls ! The same may happen if your neighbor picks up the phone and the cross-over phenomenon starts perturbing your communication (when two cables are parallel and close to each over for some distance part of the signal on one cable can "cross-over" and appear as a weak perturbation on the over cable). This is the only case I know where the bandwidth is not necessarily constant in time. Even then the bandwidth is not very likely to change during the typical duration of a bing measurement.

We also assume that the bandwidth is independent from the nature of the data sent. Again, modems usually compress the data before sending it which then violates this assumption. The workaround is to send random data which is then incompressible. But this only a partial solution because we can only randomize the packet payload, not its TCP/IP header. So for small packets, where the ratio header size / payload size is high, the bandwidth will be slightly different than for big packets.

We assume that the bandwidth does not depend on the amount of packets sent. This is incorrect if the network link is an aggregate of multiple links. Take for instance a server with four fast ethernet network cards will all the same IP address. Such a server is usually connected to a fast ethernet switch which does load balancing of the traffic on the four server's network cards. In such a situation packets individually "travel" at 100Mbps but we can have four of them travelling at once which makes the aggregate bandwidth 400Mbps. Since the server has a single IP address we see this type of link as a single network link with a 400Mbps bandwidth.
As another example consider the case of a linux box configured as a gateway to the internet by aggregating the bandwidth of two or more modems. In this case too the resulting aggregate link is capable of sending more than one packet simultaneously which results in an aggregate bandwidth which is higher than the rate at which each packet is being transmitted. And in this case all links may not have the same speed. One may be a 19.2kpbs modem while the other may be a 56kbps modem resulting, in addition, in changes in the rate at which a packet is being sent depending on which modem it goes through. (!!) do the boxes have the same IP address on both modems in such a case ?
Finally we can contrast the cases above with that of "shotgun" modems.As far as I understand, these modems aggregate two phone lines together but do so at the bit level which means that a TCP/IP packet is being sent on both lines simultaneously. So in this case the assumption that the bandwidth does not depend on the number of packets is valid.

The assumption that the latency does not depend on time must be true in all but the most extreme cases. A non negligible component of the latency is the length of the network link. The data travels approximately at the speed of light so the longer the distance the higher the latency. One sample case where it may change over time is if the network link actually goes through a low orbit satellite. In such a case the distance sender-satellite-receiver may change a lot as the satellite orbits around the earth. But such network links are currently very rare.

6.3. Measurement methodology

First we must notice that we cannot measure the round-trip-time as defined above and even less the time it takes for a network packet to go from one host to another. In both cases we would need hardware network probe.

What we can do though is measure the time it elapsed between when our software called the method to send the packet and when our software received the packet on the other side. But even this is not practical since we would have to install our software on all the hosts.

So instead we measure the rtt.

6.4. Measurement pitfalls

6.4.1. Routing problems

6.4.2. latency/delays

6.4.3. Buses, bridges and switches

It is quite likely that there will be devices and intermediaries between two hosts. Some are internal to the computer and others are network devices which are usually used to extend the reach of a network. All these intermediaries can be split into three categories.

Immediate retransmission, same bandwidth

This kind of device starts retransmitting a network frame as soon as a fixed amount of data has been received. One such kind of device are devices that don't even know what a frame is. Modems are one such kind of device. They only know about bytes and start retransmitting those bytes as soon as they have filled they transmit buffer. Another kind of device that follows this kind of rule is the network hub like ethernet repeaters. As soon as they have received the start of an ethernet frame they start retransmitting it on the other ports. Since this works both ways if a collision occurs the frame will be dropped the and the initiator will retransmit.

How does this kind of device affect the bing measures?

Let's call d the number of bytes the device must receive before it starts retransmitting the frame on the other side of the link. The device will have to wait until it has received d bytes before it can start retransmitting data. Then the time it takes to retransmit the data is overlapped with the time it takes to receive it. So the one-way trip time is:

So such a device is not going to affect our measure of the bandwidth. The only thing we will notice is a slightly increased link latency.

Immediate retransmission, different bandwidth

This kind of device bridges two links of different bandwidths. We further assume that it is bridging a slow link to a faster link. The reverse case is in fact equivalent to the previous type of device. What this device does is that it first waits until it has bufferized enough data to start transmitting to the faster link without running out. Should the frame on the slow link turnout to be invalid, due to a collision or a link failure, it would reproduce a similar condition on the other link so that the data is ignored anyway.

How does this kind of device affect the bing measures?

Let's call respectively b_s and b_f the bandwidth of the slow and fast links. The device can start retransmitting data only once the time it takes to transmit all the data on the fast link plus some buffer delay of d bytes is the same as the time it takes to receive the remainder of the data from the slow link.

So the total transmission time will be the same as the time it takes to receive all of the data at the slow link speed plus the time to build the buffer and the time to retransmit it on the fast link.

So we essentially have the same result as in the previous case except that the latency is slightly lower.

Store and forward

This kind of device, by far the most common, waits until it has received all the data from the first link and then retransmits it on the other link. This is what any router and probably most switches do. But this is also how your network card works. It waits until it has received all the data via the PCI/ISA bus and then retransmits it on the second link, the ethernet or fast ethernet link.

How does this kind of device affect the bing measures?

Let's call b₁ and b₂ the bandwidth of the two links. The device will also introduce some delay but this time it is better described in terms of time rather than in terms of bytes, so let's call it l. There is absolutely no overlap between the receive phase and the transmit phase so the one-way trip time is:

This means that the bandwidth measured by bing is going to be:

In other words, bing is going to measure the geometric mean of the links bandwidths.

Some examples:

• Take an old Ethernet card, an 8bit ISA card in a 8MHz ISA bus (PC-AT standard). These cards normally operate in half duplex mode (it's usually even worse) but what is more important to us is that, like their more modern couterparts, you first have to transfer the packet to the card buffer before it is sent on the ethernet. So such cards operate in "Store and Forward" mode. So applying the rules described above the badwidth that will be measured by bing will be, at most, the geometric mean of the bandwidth of the ISA bus and the ethernet. Since the ISA bus described above has a maximum bandwidth of 72Mbps this gives us a maximum of about 8.8MBps. Note that this is a theoretical maximum. If the card imposes some overhead for transfering data to its buffers you will not take benefit of the the full bandwidth of the ISA bus and the resulting bing measurement will be even lower.
• Let's do the same exercise in a more modern setting. Let's take a 32bits 66MHz PCI bus and a fast ehternet card. The PCI bus bandwidth is 2014Mbps and the fast ehternet bandwidth is 100Mbps so the maximum bing will ever see is about 95Mbps. Now replacing if you replace the fast ethernet card by a gigabit ethernet card it gets even worse: bing will only measure 668Mbps.
• Let's consider a fast ethernet network composed of PCs with 32bits 66MHz PCI network cards. Let's further assume that each PC is connected to an ethernet switch operating under the "Store and forward" principle. Will be the result returned by bing? Bing will think there is just one network link since it has only two IP addresses: that of the localhst and that of the other PC. But in fact the packet goes through 4 links: a PCI bus, a fast ethernet segment, another fast ethernet segment and another PCI bus. So the maximum bandwidth returned by bing will be the geometric mean of all these which gives 47Mbps.

Are these results significant?

It depends on the combined ability of the hardware and your application to overlap data transfers.
In the first example it is very unlikely that the network card will let you tranfer a packet to its buffer while it is sending the content of another buffer to the network. This means the hardware prevents you from overlapping transfers from memory to the card and from the card to the network. This means you will not be able to send data faster than what big tells you.
In the example involving the network switch you can in fact transfer data on the first network segment while the previous packet is being transfered on the second segment. But this depends on your application. An RPC based client/server application that has to wait until it gets the result of an RPC before it can do more work and issue the next one will be limited by the presence of the switch because the switch doubles the latency. Not only is the 'b' factor of the linear regression probably the double of what it would be with a direct connection but the bandwidth as measured by bing too is just half of what it would be without the switch. So the performance of RPC based applications should closely match the results of bing.
On the other hand the performance of applications like ftp will not be accurately predicted by bing's results because they can overlap multiple data transfers. Modern fast ethernet PCI cards are very likely able to transfer data to or from memory while sending or receiving data to or from the network. So in the switch example above we could have up to four packets in flight at any time. In such cases the bandwidth is limited by the slowest link, the fast ethernet link, ad the ability of the networking protocol implementation to efficiently use it (and that is not a given).

7. The architecture

9. References

Other bandwidth measuring related links:

• Bing 1.0 of course. It allows you to measure the bandwidth of a specific network link.
  http://web.cnam.fr/reseau/bing.html
  ftp://ftp.lip6.fr/pub/networking/bing-1.0.4.tar.gz
  http://www.multimania.com/fgouget/bing/
• Van Jacobson has done some work on network bandwidth measurements. There is a nice paper on the subject that he has given at the MSRI. The files claim that the source will be available soon, as soon as the code has been cleaned up, but actually I did not see any status chane in the last two years.
  The MSRI paper in Postscript and PDF
  ftp://ftp.ee.lbl.gov/pathchar/: the binaries
  http://www.caida.org/Pathchar/pathcharnotes.html: Usage notes (the binary packages don't contain a man page)
• There is is a nice paper by Kevin Lai and Mary Baker describing a smart technique for efficiently measuring the bottleneck bandwidth of a complete network path. They call their technique "Receiver Only Packet Pair". http://mosquitonet.stanford.edu/~laik/projects/nettimer/publications/infocom1999/html/
• Nettimer is a project to do passive end-to-end network performance measurement. Passive means it uses existing traffic to take measurements and end-to-end that it does not need special information from the network. It measures the bottleneck bandwidth, the latency and the available bandwidth. This tool is at least partly based on the "Packet Pair" technique described above.
  http://mosquitonet.stanford.edu/~laik/projects/nettimer/
• Bprobe and cprobe use packet dispersion techniques, similar to the Packet Pair technique, to measure network bandwidth. bprobe measures the bottleneck badwidth while cprobe measures the available bandwidth by sending a short burst of packets.
  http://www.cs.bu.edu/students/grads/carter/tools/Tools.html

Ping tools:

• ping: There are tons of ping tools available. I will only cite one, the one I wrote as an excercise to learn how to use the Windows icmp dll. Note that it's not the most sophisticated nor the most featureful ping around (although it does have one or to features that the standard Windows ping does not have).
  http://www.multimania.com/fgouget/bing/
• fping: fping allows you to efficiently ping many hosts typically to determine whether they are up or not. Using fping is more efficient than using a script which would ping the hosts in a round-robin fashion because the script would have to wait for one RTT for each host. For 1000 hosts and more this can take a while. Also fping is made to be used in scripts and its output is easy to parse which may be a reason to use it even for only a few hosts.
  http://www.stanford.edu/~schemers/docs/fping/fping.html
  ftp://ftp.lip6.fr/pub/networking/fping-2.0.tar.gz
• echoping: This tool by Stephane Bortzmeyer is designed to approximately evaluate the performance of a remote host by sending it TCP "echo" (or other protocol) packets. Unlike the ICMP echo packets, the packets sent by echoping actually require that a server process answer so that one can more easily detect if the remote host is completely overloaded or partly out of order.
  http://www.ensta.fr/internet/unix/sys_admin/echoping.html
  ftp://ftp.internatif.org/pub/unix/echoping/echoping-2.2.0.tar.gz
• traceroute: not quite a ping tool but I did not want to create a new section. You will find the sources at the URL indicated below.
  ftp://ee.lbl.gov/traceroute-1.4a5.tar.Z

You can find a more complete and very good taxonomy of network measurement tools at the following URL: http://www.caida.org/Tools/taxonomy.html.

Libpcap is a library which provides a system-independent interface for packet capture.
ftp://ee.lbl.gov/libpcap-0.4.tar.Z Found this in the Wine list (by gerard patel ): #ifdef __i386__ typedef unsigned long long u64; inline u64 gettick() { u64 ticks; asm volatile ("rdtsc" : "=A"(ticks)); return ticks; } u64 u1, u2; #endif Might be interesting if I could change it to milliseconds. Does this require to be root ?