Online Multi-level Aggregation with Delays and Stochastic Arrivals

Mathieu Mari, Michal Pawlowski, Runtian Ren, Piotr Sankowski

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: GEN achieves a constant RoE of 210 for any arbitrary tree under Poisson arrivals.
  • Component Performance: The INSTANT strategy achieves an RoE $< 8.44$ for light instances, while the PLAN strategy 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

Abstract

This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. In this problem, we are given an edge-weighted rooted tree $T$, and we have to serve a sequence of requests arriving at its vertices in an online manner. Each request $r$ is characterized by two parameters: its arrival time $t(r)$ and location $l(r)$ (a vertex). Once a request $r$ arrives, we can either serve it immediately or postpone this action until any time $t > t(r)$. We can serve several pending requests at the same time, and the service cost of a service corresponds to the weight of the subtree that contains all the requests served and the root of $T$. Postponing the service of a request $r$ to time $t > t(r)$ generates an additional delay cost of $t - t(r)$. The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The current best algorithm for this problem achieves a competitive ratio of $O(d^2)$ (Azar and Touitou, FOCS'19), where $d$ denotes the depth of the tree. Here, we consider a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm which achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant. Our algorithm is obtained by carefully combining two strategies. In the first one, we plan periodic oblivious visits to the subset of frequent vertices, whereas in the second one, we greedily serve the pending requests in the remaining vertices. This problem is complex enough to demonstrate a very rare phenomenon that ``single-minded" or ``sample-average" strategies are not enough in stochastic optimization.
BibTeX
@inproceedings{mari2024online,
  author = {Mathieu Mari and Michal Pawlowski and Runtian Ren and Piotr Sankowski},
  title = {{Online Multi-level Aggregation with Delays and Stochastic Arrivals}},
  booktitle = {ISAAC},
  year = {2024},
  doi = {10.4230/lipics.isaac.2024.49},
}
Figure