A Multi-Packet Model

In this section we describe a deterministic multi-packet model that is more powerful than the models described in the previous section and show how it can be used to measure link bandwidths along a path. The new model takes into account all the packets in a single flow as well as latency. We developed the multi-packet model as a result of attempting to unify the one-packet and packet pair models. In fact, as we show below, the multi-packet model can derive both the one-packet and packet pair models as well as the new tailgating technique.

Multi-Packet Delay Equation

The multi-packet model consists of a delay equation derived from two other equations: an arrival time equation and a queueing delay equation. The following arrival time equation is a slight variation on the one-packet equation (1) (variables defined in Table 1):

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

This equation predicts that packet k arrives at link l at its transmission time (t^k₀) plus the sum over all the previous links of the latencies (d_i), transmission delays $\left(\vphantom{\frac{s^k}{b_i}}\right.$${\frac{s^k}{b_i}}$$\left.\vphantom{\frac{s^k}{b_i}}\right)$, and queueing delays (q^k_i) of those links. Equation 3 differs from the one-packet equation (1) in that it considers k - 1 packets in the same flow and the queueing delays of those packets.

Figure: This figure shows the amount of time several packets from a flow spend on links l - 1 and l. In this example, s^{k - 1} = 4000 bits, s^k = 2000 bits, s^{k + 1} = 12000 bits, b_{l - 1} = 2Mb/s, d_{l - 1} = 2ms, b_l = 1 Mb/s, d_l = 3ms. Packet k is queued at link l for q^k_l = max$\left(\vphantom{0, 11 - 3 - 5}\right.$0, 11 - 3 - 5$\left.\vphantom{0, 11 - 3 - 5}\right)$ = 3ms. Packet k + 1 arrives 1ms after packet k leaves because something delayed it earlier in the path.

We model the queueing delay due to other packets in the same flow using the following equation:

$$\left(\vphantom{0, t^{k-1}_{l+1} - d_l - t^k_l}\right. \left.\vphantom{0, t^{k-1}_{l+1} - d_l - t^k_l}\right)$$ (4)

This equation predicts that packet k is queued at the router just before link l from the time it arrives at that router (t^k_l) until it can begin transmitting, which is the time when the previous packet (k - 1) arrives at the next router ( t^{k - 1}_{l + 1}) minus the latency of this link (d_l). We assume that the first packet is never queued ( q⁰₀ = ... = q⁰_{n - 1} = 0). An example of using Equation 4 to compute queueing delay is shown in Figure 4. This equation is equivalent to those described by Paxson [15] and Stoica [18]. Notice that packet k + 1 in the figure is not queued at all because it arrives at link l after packet k has been transmitted. Queueing delay cannot be negative, so the max() function in the queueing equation causes it to be 0 in this case.

We combine Equations 3 and 4 to form the multi-packet delay equation:

$$\sum_{i=0}^{l-1} \left(\vphantom{\frac{s^k}{b_i} + d_i + \max\left(0, t^{k-1}_{i+1} - d_i - t^k_i\right)}\right. {\frac{s^k}{b_i}} \left(\vphantom{0, t^{k-1}_{i+1} - d_i - t^k_i}\right. \left.\vphantom{0, t^{k-1}_{i+1} - d_i - t^k_i}\right) \left.\vphantom{\frac{s^k}{b_i} + d_i + \max\left(0, t^{k-1}_{i+1} - d_i - t^k_i\right)}\right)$$ (5)

The multi-packet equation is as least as powerful as both the one-packet and packet pair models because we can derive both of those models from Equation 5. We reduce the multi-packet equation to the one-packet equation (1) by taking k = 0. To derive the packet pair equation from Equation 5 we reformulate the packet pair equation as the following property:

Theorem 3.1 (Packet Pair Property)   Let
b_min(l)$\le$b_i,($\forall$i, 0$\le$i$\le$l ), then if we send two packets of the same size (s⁰ = s¹) with a small time difference ( t¹₀ - t⁰₀ < = ${\frac{s^1}{b_{min(n-1)}}}$) and there is no cross traffic, they will arrive with a difference in time equal to the size of the second packet divided by the smallest bandwidth on the path ( t¹_n - t⁰_n = ${\frac{s^1}{b_{min(n-1)}}}$).

Using Equation 5, we derive the Packet Pair Property in Appendix A.

As well as combining the advantages of previous models, the multi-packet model combines the assumptions of previous models. The model assumes that packets from other flows do not cause queueing in the modeled flow. As with previous models, this assumption can be worked around by using the minimum of several observed delays of particular packet size. Like previous models, it assumes that transmission delay is linear with respect to packet size and that routers are store-and-forward.

Link Bandwidth Measurement

In addition to deriving previous models, we use the multi-packet model to develop a new technique for link bandwidth measurement. To do so we assume that we can send one packet with no queueing and a second packet that queues behind the first packet at a specific link, but not at any later link. We describe how we ensure this assumption in practice in Section 4.

The basic approach we take is to start with the multi-packet delay equation and try to solve for the bandwidth b_lq of the link l_q at which queueing occurs. We rewrite Equation (5) to state the time packet k takes to arrive at the destination link n (with variables defined in Table 1):

t^k_n = t^k₀ + $$\sum_{i=0}^{n-1}$$$$\left(\vphantom{\frac{s^k}{b_i} + d_i + \max\left(0, t^{k-1}_{i+1} - d_i - t^k_i\right)}\right.$$$${\frac{s^k}{b_i}}$$ + d_i + max$$\left(\vphantom{0, t^{k-1}_{i+1} - d_i - t^k_i}\right.$$0, t^{k - 1}_{i + 1} - d_i - t^k_i$$\left.\vphantom{0, t^{k-1}_{i+1} - d_i - t^k_i}\right)$$$$\left.\vphantom{\frac{s^k}{b_i} + d_i + \max\left(0, t^{k-1}_{i+1} - d_i - t^k_i\right)}\right)$$

Assuming no queuing except at the queuing link, we can split this delay into the time to travel to the queueing link, the time spent at the queueing link, and the time spent after the queueing link:

$$\begin{split} t^k_n & = \left[t^k_0 + \sum_{i=0}^{l_q-1}\left... ...+ 1}^{n-1}\left(\frac{s^k}{b_i} + d_i\right)\right] \end{split}$$

We substitute using (5) and simplify:

$$\begin{split} & = t^{k}_{l_q} + \frac{s^k}{b_{l_q}} + t^{k-1... ...=l_q + 1}^{n-1}\left(\frac{s^k}{b_i} + d_i\right) \end{split}$$

We substitute using (5), include the assumption that the first packet experiences no queueing, and simplify:

$$\begin{split} & = \frac{s^k}{b_{l_q}} + \sum_{i=0}^{l_q}\lef... ...ght) + t^{k-1}_0 + \sum_{i=0}^{n-1}\left(d_i\right) \end{split}$$

Before continuing with the derivation, we define the following variables for more compact notation:

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

Using these definitions, we continue simplifying the equation:

$$\begin{split} & = \frac{s^{k-1}}{b_{l_q}} + s^{k-1}\sum_{i=0}... ...frac{1}{b^{l_q-1}}\right) + t^{k-1}_0 + d^{n-1} \\ \end{split}$$

Solving for b_lq and collecting terms,

$$\begin{split} b_{l_q} & = \frac{s^{k-1}}{(t^k_n + \frac{s^k -... ...q-1}} - \frac{s^k}{b^{n-1}} - t^{k-1}_0 - d^{n-1})} \end{split}$$ (6)

This shows that we can compute the bandwidth of a link at which queuing occurs (b_lq) from the sizes of the two packets ( s^{k - 1}, s^k), the arrival time of the second packet (t^k_n), the transmission time of the first packet (t^{k - 1}₀), the bandwidth of all earlier links (b^{l_q - 1}) and (b^{n - 1}), and the delay of all earlier links (d^{n - 1}). To use this equation in practice, we have to solve various problems including calculating the inter-packet transmission time, dealing with clock skew, and using round trip measurements. We describe our solutions to these and other implementation problems in the next section.