Previous Work

In this section, we describe previous work using deterministic models to measure link bandwidth. Deterministic models are typically easier to work with mathematically than stochastic models, enabling us to find an analytical solution rather than a numerical one. Unfortunately, a deterministic model implies modeling events with absolute certainty, and many things cannot be known with enough certainty to make this practical. Although the Internet qualifies as a system where many things cannot be known with certainty, some aspects of Internet behavior can be reasonably described using a deterministic model. In particular, previous work on bandwidth measurement has used a deterministic model along with filtering to fit empirical data to that model.

The One-Packet Model

Table 1: Variable Definitions.

n links	hop length of the path
dl sec.	latency of link l
dl sec.	sum of latencies up and including link l
bl bits/sec.	bandwidth of link l
sk bits	size of packet k
tkl sec.	time when packet k fully arrives at link l
qkl sec.	amount of time packet k is queued at link l
lbn link number	the bottleneck link

Bellovin [1], Jacobson [8], and Downey [4] measure link bandwidths using what we call the one-packet model for packet delay. This model uses the following equation (variables defined in Table 1):

$$\sum_{i=0}^{l-1} \left(\vphantom{\frac{s^0}{b_i} + d_i}\right. {\frac{s^0}{b_i}} \left.\vphantom{\frac{s^0}{b_i} + d_i}\right)$$ (1)

Figure: This figure shows the amount of time a packet spends on links 0 and 1. In this example, s⁰ = 6000 bits, b₀ = 2Mb/s, d₀ = 2ms, b₁ = 3 Mb/s, d₁ = 5ms. This packet travels across these two links in t⁰₂ = $\sum_{i=0}^{1}$$\left(\vphantom{\frac {s^0}{b_i} + d_i}\right.$${\frac{s^0}{b_i}}$ + d_i$\left.\vphantom{\frac {s^0}{b_i} + d_i}\right)$ = 12ms.

This equation predicts the time needed for one packet to travel across the l - 1 links before the lth node. Each link contributes some amount of transmission delay $\left(\vphantom{\frac{s^0}{b_i}}\right.$${\frac{s^0}{b_i}}$$\left.\vphantom{\frac{s^0}{b_i}}\right)$ and latency (d_i). The transmission delay is due to the time that a router takes to copy a packet around in buffers and serialize a packet onto a link. The latency is due to the time for a signal to travel at the speed of light, the time for a router to look up routes in a routing table, and other fixed per-packet delays that a router incurs before it can forward a packet. An example of using the one-packet model to obtain packet delay is shown in Figure 1.

The one-packet model assumes that the transmission delay is linear with respect to packet size, routers are store-and-forward, links are single-channel, and no other traffic in the path causes the measurement packet to queue. The assumption that transmission delay is linear with respect to packet size may not be true if, for example, a router manages its buffers in such a way that a 128 byte packet is copied more than proportionally faster than a 129 byte packet. However, this effect is usually small enough to be ignored. The assumption that routers are store-and-forward (they receive the last bit of the packet before forwarding the first bit) is almost always true in the Internet.

A more limiting assumption is that links are composed of only one channel. This assumption is a result of the model considering only one packet. In practice, some links stripe traffic packet by packet across multiple channels to make them appear as one link. For example, BRI ISDN links are usually composed of two 64Kb/s channels in parallel. Equation 1 will detect this as a single 64Kb/s link [4].

The final and most problematic assumption is that other traffic does not cause the measurement packet to queue. The assumption arises from the deterministic nature of the model: we do not know when the other packets were sent and what size they are, so we cannot model them deterministically. In the Internet, this assumption is almost always false. In the next section, we describe how one-packet techniques work around this.

We describe a multi-packet model in Section 3 that is able to detect multi-channel links and to use intra-flow packets (i.e., from the same source and to the same destination) for better measurement. However, the model shares the assumptions that transmission delay is linear with packet size and that no extra-flow packets in the path will cause the measurement packets to queue.

One-Packet Techniques

Figure: This figure illustrates how the one-packet model and linear regression are used to determine bandwidth. The graph shows several hypothetical measurements of the round trip delay of packets of different sizes traveling along the same path. The gray samples experienced queueing. The black samples did not experience queueing. The line is the linear regression of the black samples. The inverse of the slope is the bandwidth of the path.

Bellovin and Jacobson use the one-packet delay model to develop a technique for measuring link bandwidths. Although Equation 1 specifies the one-way delay, Bellovin and Jacobson instead use the round-trip delay to successive routers along a path. The round-trip delay can be modeled as the sum of the one-way delay for the initial packet and that of its acknowledgement.

Bellovin and Jacobson resolve the problematic assumption about no queueing by observing that queueing caused by additional traffic can only increase delays. Therefore, the minimum of several observed delays of a particular packet size fits the model. Their technique is to send several packets for each of several different packet sizes, plot the delays of these packets versus their sizes, and then use linear regression (Figure 2) to obtain the slope of the graph. The inverse of the slope is the bandwidth.

In practice, the problems with this technique are that linear regression is expensive, routers are not built to send acks in a timely manner, some nodes are ``invisible'', and the reverse path adds noise.

The first problem is that the linear regression described above must be done for every link measured. Many packets may be required to filter out the effect of other traffic and calculate a regression with high confidence. Jacobson [7] provides pathchar as an implementation of the algorithms just described. Using its default settings, it will send 10MB of data in the course of measuring a 10 hop Ethernet path [10].

Downey [4] uses statistical methods to reduce measurement traffic. Once he detects the convergence of a link bandwidth estimate, then he avoids sending further packets to measure this link. Methods such as this are complementary to our packet tailgating technique.

The second problem is that the one-packet technique requires getting timely acknowledgements from routers. Bellovin uses Internet Control Message Protocol (ICMP) Echo and Echo Reply packets sent to the routers, while Jacobson and Downey use UDP packets, successively incrementing the IP Time-To-Live (TTL) field to receive ICMP time exceeded responses from the routers.

These approaches have the advantage that no special software needs to be deployed on routers to gather timing information, but unfortunately they may not work in all parts of the Internet. Because of malevolent use of ICMP packets, some routers and hosts either rate-limit them or filter them out [16], thus slowing down or precluding measurement.

Another problem is that bridges, host operating systems (OSs), and network interface cards (NICs) are usually store-and-forward nodes but do not decrement the IP TTL and are not individually addressable in IP. Consequently, the links corresponding to these ``invisible'' nodes cannot be detected or measured using the IP TTL decrement method cited above. There is a node between the source application and the source operating system because the sending OS usually must copy packets from the application's address space to the kernel's. In addition, the source OS's network card driver usually must copy the sent packet from kernel address space across the system bus to the NIC. Finally, if the destination is a PC, the packet usually must be copied from the destination's NIC to the destination's kernel address space. The application-kernel, kernel-NIC, and NIC-kernel copies usually must be individually complete before the packet can be forwarded any further in the pipeline. These invisible nodes cause error in the measurement of the next link.

The final problem is that relying on acknowledgements and round-trip delays means that there is twice the possibility that queueing could corrupt a sample when compared to a technique that relies only on one-way delay. This is because queueing in the reverse path can delay the acknowledgement, even if there is no queueing in the forward path. As a result, many packets may be required to filter out the effect of other traffic and calculate a regression with high confidence. To use one-way delay, one-packet-based techniques to use one-way delay would need new software at every router on a path, which would not be practical.

The packet tailgating technique described in Section 4 can overcome most of these limitations. It performs linear regression only once instead of once for each link. Because it does not rely on timely delivery of acknowledgements from routers, it is robust against routers that generate ICMP packets inconsistently. Finally, it can increase accuracy and reduce the number of packets sent by measuring one-way delay instead of round trip delay, without requiring new software at routers. Packet tailgating still suffers from the invisible node problem; we partially address it in our implementation described in Section 4.1.

The Packet Pair Model

Some applications are only interested in the smallest bandwidth link along a path (the bottleneck link) rather than the bandwidths of all links in a path. An advantage of measuring bottleneck bandwidth is that it can be done with as few as two packets instead of thousands. Bolot [2], Carter and Crovella [3], Paxson [14], and Lai and Baker [10] use the packet pair model and technique to measure the bottleneck bandwidth.

Figure: This figure shows two packets of the same size traveling from the source to the destination. The wide part of the pipe represents a high bandwidth link while the narrow part represents a low bandwidth link. The spacing between the packets caused by queueing at the bottleneck link remains constant downstream because there is no additional downstream queueing.

In contrast to the one-packet model described in Section 2.1, packet pair in FIFO-queueing networks uses a two-packet model. This model predicts the difference in arrival times of two packets of the same size traveling from the same source to the same destination:

$$\left(\vphantom{\frac{s_{1}}{b_{l_{bn}}}, t^1_0 - t^0_0}\right. {\frac{s_{1}}{b_{l_{bn}}}} \left.\vphantom{\frac{s_{1}}{b_{l_{bn}}}, t^1_0 - t^0_0}\right)$$ (2)

The variables in this equation are defined in Table 1. The intuitive rationale for this equation (we give an analytical one in Appendix A) is that if two packets are sent close enough together in time to cause the packets to queue together at the bottleneck link ( ${\frac{s_{1}}{b_{l_{bn}}}}$ > t¹₀ - t⁰₀), then the packets will arrive at the destination with the same spacing ( t¹_n - t⁰_n) as when they exited the bottleneck link ( ${\frac{s_{1}}{b_{l_{bn}}}}$). The spacing will remain the same because the packets are the same size and no link downstream of the bottleneck link has a lower bandwidth than the bottleneck link (as shown in Figure 3, which is a variation of a figure from [6]).

This algorithm makes several assumptions that may not hold in practice. First, the packet pair model assumes that the two packets queue together at the bottleneck link and at no later link. This could by violated by other packets queueing between the two packets at the bottleneck link, or packets queueing in front of the first, the second or both packets downstream of the bottleneck link. If any of these events occur, then Equation 2 does not hold. In practice, previous work mitigates this limitation by filtering out samples that suffer undesirable queueing.

In addition, this model assumes that the two packets are sent close enough in time that they queue together at the bottleneck link. Carter actively sends traffic for measurement purposes to guarantee that this is the case. Paxson and Lai avoid this cost by using existing TCP traffic.

Another assumption is that the bottleneck router uses FIFO-queueing. If the router uses weighted fair queueing, then packet pair measures the available bandwidth of the bottleneck link [9].

Finally, the packet pair model, like the one-packet model, assumes that transmission delay is linear with respect to packet size and that routers are store-and-forward.

In contrast to the one-packet model, an extension to packet pair avoids the assumption that links are single-channel by considering bunches of more than two packets [14]. This extension is also able to consider other packets in the same flow. Unfortunately, it does not consider the per-link latencies taken into account in the one-packet model. The multi-packet model we present in the following section considers both.