In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication

​​​(extended Berkeley Packet Filter) is a powerful technology allows running custom code in the kernel space without modifying the kernel itself [32]. It provides a safe and efficient way to extend the functionality of the kernel and optimize various aspects of the system. eBPF programs are written in a restricted C-like language and are verified for safety before being loaded into the kernel. They can be attached to various kernel hooks and events, such as network packet processing, system calls, and function entry/exit points.

​​​(eXpress Data Path) is an eBPF-based mechanism for high-performance packet processing [32]. It allows eBPF programs to be executed at the earliest point in the network stack, directly upon packet arrival from the NIC. By processing packets at such an early stage, XDP enables low-latency and high-throughput packet processing, making it suitable for use cases like packet filtering, load balancing, and network monitoring.

​​​(Traffic Control) is another key component of the eBPF ecosystem that enables traffic control and packet manipulation [35]. It allows attaching eBPF programs to the traffic control subsystem of the kernel, enabling advanced packet classification, shaping, and scheduling. TC eBPF programs can inspect and modify packets based on various criteria, such as packet headers, protocol fields, and custom metadata. By leveraging eBPF, XDP, and TC, it is possible to offload certain networking operations to the kernel space, bypassing the conventional network stack and reducing the overhead of user-kernel crossings and network stack traversals. This makes eBPF a promising technology for optimizing distributed communication and improving the performance of various distributed systems and applications.

eBPF enforces a fundamental tension: programs are limited to 1M instructions with 512-byte stacks, yet must process unbounded data streams. Traditional algorithms fail here. We introduce a novel decomposition strategy using tail-call chains that partition aggregation into fixed-size chunks, effectively creating a “virtual stack” across program boundaries. This represents a new programming paradigm for resource-constrained environments.

TCP’s reliability assumes persistent connection state, which is impossible in eBPF’s stateless execution model. We present a counter-intuitive insight: group-based acknowledgments with receiver-side state reconstruction can achieve reliability without sender-side connection tracking. Our protocol leverages the fact that datacenter packet loss is bimodal (either very low or complete failure), making group ACKs surprisingly effective.

eBPF’s verifier rejects programs it cannot prove safe, forcing us to rethink protocol design. We discovered that traditional packet formats with variable-length fields cause verification failures. Our solution uses fixed-layout headers with semantic overloading, where the same bytes serve different purposes based on operation type, enabling complex protocols within verification bounds.

Aggregating ML gradients requires floating-point math, forbidden in eBPF. Rather than falling back to user space, we demonstrate that quantization at the network edge with careful precision management can maintain ML convergence while enabling pure-integer kernel processing. This challenges the assumption that ML requires floating-point communication.

These constraints force us to fundamentally rethink distributed communication design, yielding insights applicable beyond eBPF to any resource-constrained or verified execution environment.

The broadcast protocol in AggBox is designed to efficiently disseminate data from one node to multiple nodes in the system. To achieve this, we propose a custom UDP-based protocol optimized for fast and scalable broadcasting.

The broadcast packet format builds upon the standard UDP packet structure with additional fields to facilitate efficient broadcasting. The packet format is as follows:

[UDP Header][MAGIC_NUMBER][MASK] [SEQ_NUM][PAYLOAD]

The MAGIC_NUMBER is a 4-byte predefined value used by the eBPF program attached to the TC hook to quickly identify and process broadcast packets without deep packet inspection. The MASK is a 4-byte bitmask representing the set of destination nodes to which the packet should be broadcasted. The eBPF program performs a bitwise AND operation between this mask and the node index to determine the target nodes for broadcasting. The SEQ_NUM field is a 4-byte sequence number used for retransmission and acknowledgment purposes. It enables reliable broadcasting by allowing the sender to track the status of each packet and retransmit lost packets if necessary. The PAYLOAD contains the actual data to be broadcasted, and it is structured to fully utilize the maximum transmission unit (MTU) to optimize network utilization and avoid fragmentation.

The aggregation protocol in AggBox is designed to efficiently combine data from multiple nodes into a single result. The aggregation packet format is defined as follows:

[UDP Header][MAGIC_NUMBER][KEY][SEQ_NUM] [FRAG_OFFSET] [AGGR_OP]
[LAST_FRAGMENT] [PAYLOAD]

The MAGIC_NUMBER is used to identify aggregation packets. The KEY field is a unique identifier for the sender, allowing the aggregation program to differentiate between data from different sources, This is important for federated learning aggregation tasks where each client is assigned a different weight. The SEQ_NUM field is a sequence number used for retransmission and acknowledgment purposes, ensuring reliable delivery of aggregation packets.

The FRAG_OFFSET field indicates the starting position of the packet data within the complete data stream in the aggregated result. This allows AggBox to handle large data streams that need to be fragmented into multiple packets. The LAST_FRAGMENT field is a flag that indicates whether the current packet is the last fragment of the data stream.

The AGGR_OP field specifies the aggregation operation to be performed on the data. AggBox defines an enumeration type for the supported aggregation operations, which currently include:

• $\mathrm{■}$

  SUM: Computes the sum of the values.

• $\mathrm{■}$

  COUNT: Counts the number of values.

• $\mathrm{■}$

  MAXIMUM: Finds the maximum value.

• $\mathrm{■}$

  MINIMUM: Finds the minimum value.

• $\mathrm{■}$

  AVERAGE: Calculates the average of the values.

The FRAG_OFFSET and LAST_FRAGMENT fields enable the handling of fragmented data streams, ensuring that the complete data is aggregated correctly. The runtime library’s send_aggregated_data() function formats the data according to this protocol before sending it to the in-kernel aggregation component. The eBPF program attached to the XDP hook processes the aggregation packets, extracts the relevant fields, and performs the specified aggregation operation on the data.

To handle the next-hop information for broadcasting, AggBox utilizes the bpf_fib_lookup API to retrieve the MAC addresses corresponding to the destination IP addresses. The system employs an eBPF map to store the mapping between IP addresses and their associated MAC addresses. To ensure that the MAC addresses are up to date, AggBox leverages the bpf_timer facility to periodically refresh the MAC information. A typical refresh interval is set to 1 hour, but this can be adjusted based on the specific requirements of the deployment environment.

The eBPF program responsible for broadcasting uses the bpf_fib
_lookup API to retrieve the next-hop MAC address for each destination IP. It then updates the packet headers with the appropriate MAC addresses before cloning and forwarding the packets using the bpf_clone_redirect() helper function. By utilizing the bpf_fib_lookup API and the bpf_timer facility, AggBox eliminates the need for user-space intervention and communication via Netlink sockets to update the MAC addresses. This approach streamlines the next-hop handling process and reduces the overhead associated with maintaining up-to-date MAC information in the eBPF map.

AggBox implements a user-space retransmission mechanism to handle packet loss during broadcasting operations. The broadcasting protocol includes a sequence number field (SEQ_NUM) in the packet header, as described in § 3.2. This field tracks the order of packets and detects missing ones.

On the sender side, the runtime library maintains a map of sequence numbers and corresponding broadcast packets. When a packet is sent, the sender starts a timer and waits for an acknowledgment (ACK) from the receivers. The ACK contains the sequence number of the received packet, indicating successful delivery. If the sender does not receive an ACK within a specified timeout, it assumes the packet is lost and retransmits it.

On the receiver side, the runtime library tracks received sequence numbers and sends an ACK back to the sender for each received packet. The receiver maintains a buffer for out-of-order packets. If a gap in sequence numbers is detected, indicating missing packets, the receiver waits for them to arrive. If the missing packets do not arrive in time, the receiver informs the sender of all successfully received packets, even if they arrived out of order. This enables the sender to retransmit only the missing packets, improving retransmission efficiency.

AggBox also provides a group-based acknowledgment mechanism to reduce the overhead associated with acknowledging every single packet. The packets sent by each sender are logically divided into groups of a configurable size (e.g., 1024 packets). The receiver sends an ACK for each group of packets, rather than individual packets. This approach significantly reduces the number of ACKs sent while still ensuring reliable transmission.

Our group-based retransmission appears suboptimal, resembling Go-Back-N rather than selective repeat. This is deliberate and reveals a key insight: protocol efficiency depends on environment assumptions. eBPF’s memory constraints (512KB max map size) make per-packet state impossible for large transfers. Group tracking (1024 packets/group) reduces memory by 1024×.

Crucially, this design exploits datacenter network characteristics where loss is bimodal, either near-zero (<0.01%) or total failure. With p=0.0001 loss rate, the probability of multiple losses in a 1024-packet group is $1-{(1-p)}^{1024}\approx 0.097$, and having exactly one loss is 0.088. Thus, 90% of groups need no retransmission, and most others need just one packet. This makes our “inefficient” protocol surprisingly effective in practice.

To further optimize the retransmission process, AggBox incorporates rate negotiation and aggregation node selection mechanisms. By determining the sending rate of senders and the aggregation topology based on available bandwidth and aggregator capacity, AggBox proactively minimizes the likelihood of packet loss due to network congestion or aggregator overload. This helps reduce the need for retransmissions and enhances the efficiency of the reliable transmission mechanism.

While AggBox employs a custom protocol for optimized performance, it is designed with interoperability in mind. The protocol is built on standard UDP, ensuring compatibility with existing network infrastructure including switches, routers, and firewalls that handle UDP traffic. The custom header fields (MAGIC_NUMBER, MASK, SEQ_NUM) are encapsulated within the UDP payload, making AggBox packets indistinguishable from regular UDP traffic at the network layer.

For mixed deployments where some nodes run AggBox and others do not, the system provides graceful fallback behavior. Non-AggBox endpoints can communicate using standard socket APIs since the underlying transport is UDP. AggBox receivers process packets without the magic number as regular application data, forwarding them to user space through the standard network stack.

The group-based acknowledgment mechanism is a performance optimization rather than a protocol requirement. When communicating with legacy systems or in scenarios where per-packet reliability is preferred, AggBox can operate in per-packet ACK mode at the cost of increased overhead. This flexibility allows incremental deployment, enabling organizations to adopt AggBox on a subset of nodes and expand coverage over time without disrupting existing applications.

eBPF prohibits floating-point arithmetic, yet ML workloads require gradient aggregation. Rather than falling back to user space (defeating our purpose), we exploit an insight from quantized training research: neural networks are surprisingly robust to reduced precision [26, 17, 37].

Our approach performs quantization at the network edge: senders multiply floating-point values by a scaling factor (e.g., ${10}^8$) and round to 32-bit integers. The kernel performs pure integer aggregation. Receivers divide by the factor and worker count to recover floats. This is not merely a workaround but actually reduces network bandwidth (32 vs 64 bits) and leverages the fact that gradient magnitudes in modern optimizers (Adam, RMSprop) typically range from ${10}^{-4}$ to ${10}^{-2}$, fitting comfortably in scaled integer representation.

For example, with 10,000 workers and gradient value 0.001: quantized value = $0.001\times {10}^8=100,000$. After aggregation: $100,000\times 10,000=1,000,000,000$ (well within int32). Recovery: $1,000,000,000/{10}^8/10,000=0.001$. The quantization error () is negligible compared to the inherent noise in stochastic gradient descent, which actually aids convergence through implicit regularization.

In cases where the aggregation logic is too complex to be handled entirely in the kernel, even with function chaining, AggBox provides a user-space backup mechanism. This mechanism also helps to avoid wasting DMA resources on transferring packets that cannot be fully processed in the kernel.

AggBox predefines a set of aggregation operators based on the protocol design. If an incoming packet does not match any of these predefined operators, the XDP program will redirect the packet to the user-space runtime by AF_XDP for further processing. For example, if the aggregation logic involves complex operations like matrix multiplication or non-linear transformations, the XDP program will detect this and hand over the processing to the user space. Additionally, if the XDP runtime detects that the current network conditions or the data to be aggregated persist for an extended period, exceeding a predefined threshold, it will transfer the processing to the user-space runtime. This ensures that the system can handle various situations and prevent the XDP program from being overloaded or stalled. In such cases, the packet transfer utilizes AF_XDP sockets, benefiting from kernel bypass to enhance performance.

AggBox can detect DMA resource utilization by monitoring the status and length of DMA queues, handling interrupts, utilizing performance counters and metrics, managing buffer occupancy, and using eBPF programs to gather real-time data. The user-space backup mechanism processes these packets and performs the aggregation operation using the full capabilities of the user-space environment. By selectively offloading complex aggregation operations to the user space, AggBox ensures optimal utilization of DMA resources and maintains compatibility with a wide range of aggregation scenarios.

For large-scale deployments, AggBox supports multi-level aggregation trees where intermediate nodes perform partial aggregation, reducing load on the root aggregator. This approach can scale to thousands of nodes by limiting fan-in at each level.

The INDEX_MASK mechanism supports up to 32 destinations per packet. For larger broadcasts, we employ a tree-based dissemination where each node forwards to a subset of children, enabling broadcasts to arbitrary numbers of nodes.

To handle high packet rates from many senders, we implement adaptive buffer management that dynamically adjusts ring buffer sizes based on arrival rates, preventing buffer overflow under load.

Theoretical analysis shows that with 10 Gbps links and 1KB packets, a single aggregator can handle up to 1.25M packets/second. With our measured per-packet processing time, this supports approximately 300 concurrent senders before queuing delays become significant. For larger deployments, hierarchical aggregation becomes necessary.

We evaluate the broadcast latency of AggBox compared to a baseline implementation using traditional UDP sockets. The packet size is set to the Maximum Transmission Unit (MTU) to ensure optimal network utilization.

3(a) presents the average broadcast latency for both AggBox and the baseline implementation with a varying number of receivers. The results demonstrate that AggBox consistently achieves lower latency compared to the baseline, regardless of the number of receivers. The performance gain becomes more pronounced as the number of receivers increases, indicating the scalability of our in-kernel broadcasting approach. For instance, with 9 receivers, AggBox achieves an average broadcast latency of 92.05 µs, while the baseline implementation exhibits a latency of 534.22 µs, resulting in a significant reduction of 82.8%.

To further illustrate the robustness of AggBox, 3(b) shows the 99th percentile broadcast latency. Even under high percentile latency, AggBox maintains its performance advantage over the baseline implementation, ensuring a consistently low latency for broadcasting operations. With 9 receivers, AggBox achieves a 99th percentile latency of 120.72 µs, while the baseline implementation exhibits a latency of 611.71 µs, resulting in a reduction of 80.3%.

Now, we investigate the impact of packet size on the broadcast latency. We fix the number of receivers to 9 and vary the packet size from 64 bytes to 1024 bytes. Figure 4 presents the results, comparing AggBox with the baseline implementation.

AggBox maintains consistently lower broadcast latency across all packet sizes. For 1024-byte packets, AggBox achieves 238.07 µs versus the baseline’s 265.34 µs (10.3% reduction). While AggBox’s latency remains stable (165.55-238.07 µs), the baseline shows increasing latency with packet size, demonstrating the impact of user-space processing overhead. This stability highlights the efficiency of kernel-space processing in handling varying data volumes.

To assess AggBox’s real-world impact, we integrate our in-kernel broadcasting optimizations into four distributed applications: Breadth-First Search (BFS), Depth-First Search (DFS), PageRank, and Fibonacci computation. For BFS, DFS, and PageRank, input graphs vary from 16 to 512 vertices, generated using a random graph function to ensure diverse structures. For Fibonacci, the number of recursive calls ranges from 10 to 40.

Figure 5 shows computation times for each application with varying inputs. As expected, computation time increases with input size, highlighting different computational characteristics. BFS and DFS range from microseconds for small graphs to milliseconds for larger ones (512 vertices). PageRank’s times reach hundreds of milliseconds for the largest graphs. Fibonacci’s computation time grows exponentially with the number of recursive calls.

Figure 6 compares broadcast latency between AggBox and the baseline. AggBox consistently achieves lower latency across all applications and input sizes. This performance gain is particularly notable when computation times are small, as communication overhead becomes a dominant factor.

For example, in BFS and DFS with small input graphs (16 vertices), computation time is in microseconds while broadcast latency is in hundreds of microseconds. Here, AggBox’s optimizations significantly reduce latency. For BFS with 16 vertices, AggBox achieves a latency of 130.31 µs, compared to 244.87 µs for the baseline, a 46.8% reduction. For DFS with 16 vertices, AggBox achieves 136.78 µs versus 192.67 µs for the baseline, a 29.0% reduction.

As input sizes increase and computation times grow, the impact of broadcast latency on overall performance lessens. However, AggBox still outperforms the baseline. In PageRank with 512 vertices, AggBox achieves 31.10 µs latency compared to 200.36 µs for the baseline, an 84.5% reduction. For Fibonacci with 40 recursive calls, AggBox achieves 158.22 µs latency, while the baseline is 214.44 µs, a 26.2% reduction.

These experiments demonstrate AggBox’s real-world benefits by reducing latency in diverse distributed applications. By optimizing kernel-level broadcasting, AggBox enhances communication efficiency and scalability, leading to faster execution times and better performance. Significant gains in scenarios with shorter computation times highlight the critical importance of optimizing communication for application performance.

We evaluate the aggregation throughput of AggBox compared to the baseline implementation (Socket-based) using different data sizes. We use four machines to send data and aggregate it on one machine. Figure 7 shows the results.

AggBox achieves higher aggregation throughput across all data sizes. At 512 MB, AggBox reaches 212,288,843 ops/s versus the baseline’s 54,025,990 ops/s (3.9× improvement). The widening performance gap with larger data sizes demonstrates how kernel-space aggregation eliminates the memory copy and context switch overhead that increasingly burdens user-space processing.

We evaluate the impact of computation cost on the performance of AggBox and the baseline implementation. We use XDP to add all received matrices and perform GEMM (general matrix multiplication) in the user space for AggBox, while the baseline performs both addition and GEMM in the user space. We use 4 senders and vary the matrix size (N) and measure the average time taken for the aggregation operation. Figure 8 shows the results.

As matrix size increases, computation dominates and the performance gap narrows. At matrix size 1024, AggBox takes 8.3 seconds versus the baseline’s 8.2 seconds, a negligible difference. This expected behavior occurs because AggBox optimizes communication, not computation. When GEMM operations dominate runtime, kernel-space aggregation provides minimal benefit as both systems are bound by user-space computation.

We evaluate the performance of AggBox in parameter servers using three different models: ResNet-34 [9] (vision), GPT-2 [25] (text), and Wav2Vec [2] (audio). Figure 9 shows the performance comparisons between AggBox and the baseline (socket-based) for each model.

AggBox consistently outperforms the baseline across all three models, with performance gaps widening as workers increase. The improvements stem from kernel-space aggregation of model updates, eliminating user-kernel transitions during gradient synchronization. AggBox’s consistent gains across vision (ResNet34), text (GPT-2), and audio (Wav2Vec) models demonstrate its applicability to diverse ML workloads.

To quantify the reduction in training time achieved by AggBox, we calculate the percentage improvement over the baseline for each model and number of workers. Table 3 shows the results.

The results show that AggBox achieves significant reductions in aggregation time across all models and worker configurations. For ResNet34 and Wav2Vec, the reduction in aggregation time ranges from 51.7% to 56.1%, indicating that AggBox can effectively accelerate the aggregation process by more than half. For GPT-2, the reduction in aggregation time is slightly lower but still substantial, ranging from 33.9% to 55.5%.

These findings highlight the practical impact of AggBox in accelerating distributed training workloads. By reducing the aggregation time, AggBox enables faster iterations and experimentation, which is crucial in the development and deployment of machine learning models. The significant time savings achieved by AggBox can lead to improved productivity and faster time-to-market for machine learning applications.

We evaluate the performance of AggBox in a MapReduce scenario, using a word counting job with different input data sizes (2 million to 10 million words) and varying numbers of mappers (2 to 10). Figure 10 shows the results, comparing the performance of AggBox against the baseline implementation.

AggBox significantly outperforms the baseline across all configurations. With 2 mappers and 4 million words, AggBox achieves 126.25 million words/s versus the baseline’s 5.72 million words/s (22× improvement). Performance scales with more mappers: at 10 mappers and 10 million words, AggBox reaches 257.66 million words/s compared to 5.98 million words/s for the baseline (43× improvement).

The performance gains stem from AggBox’s kernel-space aggregation eliminating user-kernel crossings during the reduce phase. Our MapReduce workload is network-bound since the reduce operations (word count summation) are simple, making communication the bottleneck. The baseline’s flat throughput across configurations indicates saturation from user-space processing overhead, while AggBox’s kernel processing efficiently handles the high packet rates from bursty mapper outputs. This demonstrates AggBox’s effectiveness for network-bound workloads where communication dominates computation.

We evaluate the CPU usage of AggBox on isolated CPUs when using different numbers of senders for aggregation operations. Figure 11 shows the CPU usage as the number of senders increases from 2 to 30.

The results demonstrate that AggBox maintains low CPU usage even as the number of senders increases. When the number of senders is 2, the CPU usage is only 1.38%, indicating that AggBox can efficiently handle aggregation operations from a small number of senders. As the number of senders increases to 10, the CPU usage remains relatively low at 6.70%. This shows that AggBox can accommodate a moderate number of senders without incurring significant overhead.

Even when the number of senders reaches 30, the CPU usage is still manageable at 29.92%. This demonstrates AggBox’s ability to scale and handle aggregation operations from a large number of senders while maintaining acceptable CPU utilization. The gradual increase in CPU usage as the number of senders grows can be attributed to the increased workload associated with handling aggregation operations from multiple senders. However, the rate of increase in CPU usage is sublinear, indicating that AggBox’s performance scales well with the number of senders.

The efficient CPU utilization can be attributed to several factors. First, AggBox’s use of eBPF and kernel-space aggregation allows for fast and efficient processing of incoming aggregation packets. By offloading the aggregation operations to the kernel space, AggBox reduces the overhead associated with user-kernel crossings and context switches.