Abstract
This work investigates the effect of finite buffer sizes on the throughput capacity and packet delay of line networks with packet erasure links that have perfect feedback. These performance measures are shown to be linked to the stationary distribution of an underlying irreducible Markov chain that models the system exactly. Using simple strategies, bounds on the throughput capacity are derived. The work then presents two iterative schemes to approximate the steady-state distribution of node occupancies by decoupling the chain to smaller queueing blocks. These approximate solutions are used to understand the effect of buffer sizes on throughput capacity and the distribution of packet delay. Using the exact modeling for line networks, it is shown that the throughput capacity is unaltered in the absence of hop-by-hop feedback provided packet-level network coding is allowed. Finally, using simulations, it is confirmed that the proposed framework yields accurate estimates of the throughput capacity and delay distribution and captures the vital trends and tradeoffs in these networks.
Introduction
In traditional network theory, researchers often assume buffers are infinite to simplify calculations. However, real-world hardware has finite memory. When a buffer fills up, it causes "blocking"—a backpressure effect where a node cannot transmit because its neighbor has no room to receive. This creates complex, non-linear dependencies between all nodes in a chain. While queueing theory has studied "tandem queues" for decades, most models use continuous-time assumptions that do not perfectly map to discrete packet-based communications. This paper bridges this gap by providing tools to calculate the fundamental limits of throughput and latency in these constrained environments.
Methodology
The authors approach the problem through three main lenses:
- Exact Markov Modeling: They define an "Exact Markov Chain" (EMC) to track the number of packets at every node. While precise, this model's state space grows exponentially with the number of hops, making it computationally intensive for large networks.
- Iterative Estimation Schemes: To make the analysis practical, they propose two approximations that decouple the network into smaller, local queueing blocks:
- Rate-based Iterative Estimate: A simpler model that assumes packet arrivals and departures are memoryless and uses a single parameter to represent the probability of a node being blocked.
- Distribution-based Iterative Estimate: A more sophisticated approach that treats the packet process as a "renewal process," tracking the full distribution of time between packet arrivals.
- Network Coding Analysis: They analyze a scenario without feedback, where nodes use Random Linear Network Coding (RLNC). They use an algebraic approach to show that as the coding field size increases, the "coded" occupancy dynamics converge to the same behavior as a system with perfect feedback.
Key Insights and Results
- The Feedback Equivalence: A significant finding is the proof that throughput capacity is unaltered by the absence of feedback, provided packet-level network coding is utilized. Coding effectively "fills the gaps" created by lost packets without requiring explicit feedback.
- High Accuracy: The proposed iterative estimates are highly effective, predicting throughput capacity within 1% error of actual simulated values.
- The Diminishing Returns of Buffers: There is a "critical buffer size" for every network. Beyond this point, adding more memory provides negligible throughput gains but causes a massive, linear increase in average latency. In an 8-hop network example, increasing the buffer size from 10 to 15 packets improved throughput by less than 1.5%, but increased the mean packet delay by 47%.
- Blocking vs. Loss: The paper highlights that in finite networks, "blocking" (due to full buffers) is just as critical as "erasure" (due to link noise) in determining the final capacity.
Conclusion and Future Work
This work provides a robust theoretical framework for analyzing the performance of line networks with lossy links and finite buffers. By modeling the system as a Markov chain and introducing efficient iterative estimation schemes, the authors demonstrate how to accurately predict throughput and delay. While currently limited to line networks with single flows, the authors suggest extending these iterative "local" analysis techniques to general network topologies and multi-source/multi-sink scenarios in future research.
Summary updated