Network
packets have common destination: rightmost node
Execution in synchronous rounds
Goal. Deliver packets using minimum space per buffer
Adversarial Queueing Theory (Borodin et al. STOC 1996)
Executions
For cenralized protocols, buffer space $2 \rho + \sigma$ is necessary and sufficient
For local protocols, buffer space $\Theta(\rho \log n + \sigma)$ is necessary and sufficient (?)
For protocols with locality $d$, buffer space $\Theta(1 + \frac \rho d \log n + \sigma)$ is necessary and sufficient
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
AQT parameters do not distinguish ($\rho = 1, \sigma = n - 1$):
Ex 1 every $n$ rounds, inject $n$ packets into buffer $1$
Ex 2 every $n$ rounds, injection $1$ packet into buffers $1, 2, \ldots, n$
But buffer space requirement is $n$ vs $1$
Locally Bursty Adversaries (LBAs)
Previous examples
LBA is strict refinement of AQT model
General capacities, $C$
apply protocol for $C = 1$ to bundles
apply protocol for $C = 1$ to bundles
apply protocol for $C = 1$ to bundles
apply protocol for $C = 1$ to bundles
Theorem 1.
Consequence. Any protocol/analysis for $C = 1$ can be applied to general $C$ as well.
Note. Analogous results for AQT model do not hold.
Odd-Even Downhill Forwarding (OED). (Dobrev et al. + Patt-Shamir & R–). Each round, buffer $i$ forwards iff
Theorem 2. For any LBA with parameters $\rho \leq 1$, $\sigma, B \geq 1$, the buffer space requirement of OED is $O(B \log n + \sigma)$.
AQT analysis had $O(\log n + \sigma)$ for $\rho \leq 1$
Theorem 2 follows from more refined analysis of OED algorithm
Theorem 3. $P$ any (possibly centralized and/or randomized) forwarding protocol, $B, \sigma \geq 1$. Then there is an LBA such that $P$ requires $\Omega(B \log n + \sigma)$ buffer space.
Consequences.
For protocols with locality $d$, buffer space $\Theta(1 + \frac 1 d \log n)$ is necessary and sufficient