Packet Pair Derivation

Before starting the derivation, we define and derive two lemmas to keep the main derivation clearer. The lemmas have no other conceptual significance.

Lemma A..1   Let s⁰ = s¹, t⁰₀ = t¹₀, 0$\le$j$\le$n. Then

t¹_j - t⁰_j = $$\sum_{i=0}^{j-1}$$max$$\left(\vphantom{0, t^0_{i+1} - d_i - t^1_i}\right.$$0, t⁰_{i + 1} - d_i - t¹_i$$\left.\vphantom{0, t^0_{i+1} - d_i - t^1_i}\right)$$

Proof.

$$% latex2html id marker 2761 \begin{split} t^1_j & - t^0_j = ... ...0}^{j-1}\max\left(0, t^0_{i+1} - d_i - t^1_i\right) \end{split}$$

$\Box$

Lemma A..2   Let s⁰ = s¹, t⁰₀ = t¹₀, 0$\le$j$\le$n. Then

t⁰_{j + 1} - d_j - t¹_j = $${\frac{s^0}{b_j}}$$ - $$\sum_{i=0}^{j-1}$$max$$\left(\vphantom{0, t^0_{i+1} - d_i - t^1_i}\right.$$0, t⁰_{i + 1} - d_i - t¹_i$$\left.\vphantom{0, t^0_{i+1} - d_i - t^1_i}\right)$$

Proof.

$$% latex2html id marker 2777 \begin{split} t^0_{j+1} & - d_j ... ...xtrm{(From Equation~\ref{eq:MultiPacketModel})} \\ \end{split}$$

$$\begin{split} & = \sum_{i=0}^{j - 1}\left(\frac{s^0}{b_i} + d... ...}^{j-1}\max\left(0, t^0_{i+1} - d_i - t^1_i\right) \end{split}$$

$\Box$

We state the packet pair property and then derive it:

Theorem A..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)}}}$).

Proof. We perform induction on n, the number of links. For n = 1, we substitute using Equation 5:

$$\begin{split} t^1_{n} & - t^0_n = t^1_{1} - t^0_1 \\ & \\ &... ...ft(\frac{s^0}{b_i} + d_i \right) + t^0_0\right) \\ \end{split}$$

We continue simplifying and substitute again using Equation 5:

$$\begin{split} & = \frac{s^1}{b_0} + d_0 + \max(0, t^0_{1} - d... ...^0_0 - t^1_0 + d_0 - d_0\right) + t^1_0 - t^0_0 \\ \end{split}$$

We simplify and use our inductive hypothesis that this path has only one link:

$$\begin{split} & = \max\left(0, \frac{s^1}{b_{min(n-1)}} + t^0_0 - t^1_0\right) + t^1_0 - t^0_0 \\ \end{split}$$

We transform one of our assumptions:

$$\begin{split} t^1_0 - t^0_0 &\le \frac{s^1}{b_{min(n-1)}} \\ t^0_0 - t^1_0 &\ge -\frac{s^1}{b_{min(n-1)}} \\ \end{split}$$

We apply the transformed assumption and simplify:

$$\begin{split} & = \frac{s^1}{b_{min(n-1)}} + t^0_0 - t^1_0 + t^1_0 - t^0_0 \\ & = \frac{s^1}{b_{min(n-1)}} \\ \end{split}$$

This proves the n = 1 case. For n > 1, we start by using Lemma A.1:

$$\begin{split} t^1_{n} - t^0_n = \sum_{i=0}^{j-1}\max\left(0, t^0_{i+1} - d_i - t^1_i\right) \end{split}$$

We simplify further and apply the inductive hypothesis:

$$\begin{split} & = \sum_{i=0}^{j-2}\left(\max\left(0, t^0_{i+1... ... \max\left(0, t^0_{n} - d_{n-1} - t^1_{n-1}\right) \end{split}$$

We apply Lemma A.2:

$$\begin{split} & = \frac{s^0}{b_{min(n-2)}} + \max\left(0, \fr... ...x\left(0, t^0_{i+1} - d_i - t^1_i\right)\right) \\ \end{split}$$

We apply Lemma A.1:

$$\begin{split} & = \frac{s^0}{b_{min(n-2)}} + \max\left(0, \frac{s^0}{b_{n-1}} - t^1_{n-1} - t^0_{n-1}\right) \\ \end{split}$$

We apply the inductive hypothesis again and simplify:

$$\begin{split} & = \frac{s^0}{b_{min(n-2)}} + \max\left(0, \fr... ...rac{s^0}{b_{min(n-2)}}, \frac{s^0}{b_{n-1}} \right) \end{split}$$

There are two possibilities at this point. One possibility:

$${\frac{s^0}{b_{min(n-2)}}}$$$$\ge$$$${\frac{s^0}{b_{n-1}}}$$

$$\ge$$ (7)

$$% latex2html id marker 2836 \begin{split} t^1_{n} - t^0_n & ... ... \textrm{(From (\ref{eq:1}) and \(s^0 = s^1\))} \\ \end{split}$$

The other possibility:

$${\frac{s^0}{b_{min(n-2)}}}$$ < $${\frac{s^0}{b_{n-1}}}$$

b_{n - 1} < b_{min(n - 2)} (8)

$$% latex2html id marker 2843 \begin{split} t^1_{n} - t^0_n & ... ... \textrm{(From (\ref{eq:2}) and \(s^0 = s^1\))} \\ \end{split}$$

$Id: main.tex,v 1.6 2001/04/04 22:35:25 laik Exp $