Abstract
This paper investigates the Online Multi-Level Aggregation (MLA) problem, a core challenge in logistics and data networking. While previous research has focused on adversarial models—resulting in pessimistic $O(d^2)$ competitive ratios—this work explores a stochastic arrival model where requests follow a Poisson process. We introduce a deterministic online algorithm, GEN, which achieves the first constant-factor approximation for this problem. By combining immediate service for low-traffic nodes and periodic scheduling for high-traffic clusters, the GEN algorithm yields a constant Ratio of Expectations (RoE) of 210, demonstrating that stochastic assumptions significantly improve the tractability of multi-level aggregation.
1. Introduction
Multi-Level Aggregation (MLA) describes scenarios where multiple requests must be consolidated to minimize service costs while managing delay penalties. A classic example is a supply chain where a central factory receives replenishment requests from various distributed convenience stores. Shipping each request individually is prohibitively expensive; however, waiting to aggregate requests into a single truck delivery incurs delay costs and reduces customer satisfaction.
In computer science, this is modeled as a rooted, edge-weighted tree where requests arrive at nodes over time. To serve a set of requests, one must pay for the edges of the minimal subtree connecting those nodes to the root. The objective is to minimize the total cost, defined as the sum of service costs and the cumulative delay of all requests.
2. Stochastic vs. Adversarial Models
Historically, MLA has been analyzed under the adversarial model, where an opponent selects the worst possible sequence of arrivals. In such cases, the competitive ratio is bounded by $O(d^2)$, where $d$ is the depth of the tree. This paper shifts the focus to a stochastic model, assuming requests arrive according to a Poisson process. This assumption is more representative of real-world systems, such as TCP acknowledgment bundling or inventory management, and allows for more optimistic performance guarantees.
3. The GEN Algorithm
The authors propose a deterministic online algorithm named GEN. The algorithm's design stems from the observation that different tree instances require distinct strategies based on their "heaviness."
3.1 The Heaviness Threshold
The paper identifies a critical parameter, $\pi = w \cdot \lambda$, where $w$ is the edge weight and $\lambda$ is the arrival rate.
- Light Instances ($\pi \le 1$): When requests are rare or edges are cheap, the INSTANT strategy—serving requests immediately upon arrival—is most effective.
- Heavy Instances ($\pi > 1$): When requests are frequent or edges are expensive, the PLAN strategy—serving nodes on a fixed, periodic schedule—is superior.
3.2 Hybrid Strategy and Balanced Partitioning
For a general tree, neither strategy is sufficient on its own. The GEN algorithm employs a balanced partition technique to decompose the tree into sub-components. It applies the INSTANT strategy to nodes near the root (where traffic is lighter relative to edge costs) and the PLAN strategy to more distant, "heavier" clusters. To ensure efficiency across levels, the PLAN strategy utilizes service periods rounded to the nearest power of two, allowing for synchronized service across different tree depths.
4. Key Results
The primary contribution of this work is the proof that the GEN algorithm achieves a constant Ratio of Expectations (RoE), which compares the expected cost of the online algorithm to the expected cost of the optimal offline solution.
- Global Performance:
GENachieves a constant RoE of 210 for any arbitrary tree under Poisson arrivals. - Component Performance: The
INSTANTstrategy achieves an RoE $< 8.44$ for light instances, while thePLANstrategy achieves an RoE $< 21.34$ for heavy instances. - Failure of Simple Strategies: The authors demonstrate that purely "greedy" or "sample-average" strategies fail on specific tree structures (e.g., depth-2 trees), where they can result in an unbounded RoE. This justifies the necessity of the hybrid approach used in
GEN.
5. Discussion and Future Work
While a constant RoE of 210 is a significant theoretical milestone, it remains high for practical implementation. Future research may focus on tightening this bound. Additionally, the authors propose the Greedy Conjecture, suggesting that a simple heuristic—serving a node when its accumulated delay equals its service cost—might also achieve a constant RoE, though this remains unproven.
Further extensions of this work could include:
- Edge Capacities: Accounting for the fact that "trucks" or data packets have finite limits.
- Multiple Roots: Expanding the model to networks with multiple distribution centers.
- Non-Poisson Arrivals: Testing the robustness of these strategies against other stochastic distributions that lack the memoryless property of the Poisson process.
Summary updated