TL;DR
This paper empirically evaluates four types of reliable multicast protocols (ACK-based, NAK-based with polling, ring-based, and tree-based) over Ethernet-connected clusters. The key takeaway is that for large messages, NAK-based protocols with polling offer the best performance on Ethernet, outperforming others due to efficient sender load and pipeline communication.
What Problem Does This Paper Address?
High-performance computing (HPC) clusters are increasingly built using clusters of workstations connected by Ethernet. While standard IP multicast offers efficient one-to-many communication, it's unreliable. To leverage multicast for HPC, reliable multicast protocols are needed. Existing reliable multicast protocols are often designed for the wide-area internet, and their performance characteristics over the specific architectural features of local area networks (LANs) like Ethernet, especially in homogeneous cluster environments, are not well understood. This paper aims to bridge this gap by empirically studying how Ethernet's features impact different reliable multicast protocols and identifying the most efficient schemes for this environment.
Methods
The authors implemented four categories of reliable multicast protocols:
- ACK-based: Receivers send positive acknowledgments (ACKs) for each packet. This can lead to an "ACK implosion" problem where the sender is overwhelmed by ACKs from many receivers.
- NAK-based with polling: Receivers send negative acknowledgments (NAKs) only when a packet is missing. To mitigate the sender's inability to know when data can be released from memory (due to lack of ACKs), a polling mechanism is incorporated.
- Ring-based: Receivers form a logical ring, and only one designated receiver (token site) sends an ACK for a packet, which is then multicasted to others. Receivers send NAKs to the token site.
- Tree-based: Receivers are organized into a hierarchy with group leaders. Leaders aggregate ACKs from their subgroups and interact with the sender. This aims to alleviate the ACK implosion problem.
The study involved implementing these protocols over UDP using the standard Linux operating system and evaluating their performance on a cluster of 31 Pentium III machines connected via Ethernet switches. They focused on communication time and throughput, varying parameters like packet size, window size, and tree height.
Datasets
Not discussed in the paper. The experiments were conducted on a custom-built cluster using synthetic data transfers.
Key Insights and Ideas
- Ethernet's impact: The low error rate and small propagation delay of Ethernet significantly influence protocol design. Unlike wide-area networks, retransmissions are rare, and large buffers are often unnecessary.
- ACK Implosion is a real problem: ACK-based protocols, while conceptually simple, suffer significantly from the sender being overwhelmed by acknowledgments, especially with a large number of receivers.
- NAK-based protocols shine on Ethernet: For large messages, NAK-based protocols with polling emerge as the most efficient. This is attributed to reduced sender load and the ability to exploit pipeline communication.
- Packet size is crucial: For most protocols (NAK, Ring, Tree), there's an optimal packet size. Very small packets lead to high overhead, while very large packets can also be suboptimal, suggesting a balance is needed.
- Tree-based protocols are not always better: While designed to solve ACK implosion, tree-based protocols can be inefficient for small messages due to the overhead of relaying messages at the user level. Their performance is also sensitive to tree structure.
- Window size matters, but not always large: For ACK-based protocols, a small window size (e.g., 2) was often optimal, as large buffers didn't improve performance due to Ethernet's low latency and competing ACK traffic. For NAK and Ring protocols, a larger window size was generally beneficial.
Key Results
- For large messages: The performance order was NAK-based > Ring-based ≥ Tree-based > ACK-based. NAK-based protocols achieved the highest throughput (e.g., 89.7 Mbps).
- For small messages: ACK-based, NAK-based with polling, and Ring-based protocols performed similarly and better than Tree-based protocols.
- ACK-based protocols: Performance is highly sensitive to packet size (larger is better) and surprisingly optimal with a small window size (e.g., 2).
- NAK-based protocols with polling: Require careful selection of packet size (medium sizes like 8KB were often best), a large window size, and an appropriate polling interval (around 80-90% of the window size).
- Ring-based protocols: Similar to NAK-based, they benefit from a medium packet size and a window size at least one greater than the number of receivers.
- Tree-based protocols: Performance depends on both tree structure (height) and packet size. They are generally better for large messages but less efficient for small messages.
Limitations and Future Work
- Limitations: The study focuses on homogeneous clusters and Ethernet. The impact of dynamic group membership changes was not considered. The paper mentions that implementation issues are omitted due to space limitations, but details can be found in a technical report [11].
- Future Work: The paper suggests that further investigation into how architectural features of Ethernet affect flow control, buffer management, and retransmission mechanisms in reliable multicast protocols is warranted. The authors also imply that understanding these impacts can lead to the development of even more efficient protocols tailored for cluster environments.
Summary updated