Online Distributed Job Dispatching with Outdated and Partially-Observable Information

Yuncong Hong, Bojie Lv, Rui Wang, Haisheng Tan, Zhenhua Han, Hao Zhou, Francis C. M. Lau

Introduction

In modern Metropolitan Area Networks (MANs), edge computing is essential for processing data near users to minimize latency and energy consumption. However, managing job dispatching in these environments is complex. Ideally, a dispatcher at an Access Point (AP) would have perfect, instantaneous knowledge of every server's status. In practice, two major hurdles exist: outdated information due to signaling delays and partial observability because collecting global state data is bandwidth-prohibitive.

System Model

The network architecture typically consists of mobile devices, APs acting as dispatchers, edge servers, and a central cloud server. APs must decide where to send incoming jobs based on local, potentially "stale" information.

Network architecture for distributed job dispatching.

Methodology

The authors formulate this challenge as a Partially Observable Markov Decision Process (POMDP). To overcome the computational complexity of standard POMDP solutions, they propose a novel approximation framework:

  • Value Function Approximation: A "Baseline Policy" is used to estimate future system costs, simplifying global optimization into local tasks.
  • Greedy Subset Partitioning: APs are grouped into subsets that update strategies asynchronously. This prevents conflicting decisions based on the same stale data, avoiding the "thundering herd" effect where multiple dispatchers overwhelm a single server.
  • Decoupled Optimization: The global problem is broken down into local problems for each AP, requiring only information about a "Conflict AP Set"—neighbors whose decisions impact the same edge servers.

Experimental Evaluation

The framework was evaluated using Google Cluster traces for realistic job patterns and a Barabási-Albert (BA) model for network topology. The simulation involved 15 APs and 10 processing servers, with signaling latencies modeled to reflect real-world MAN conditions.

Key Results

The proposed MDP policy consistently outperformed standard heuristics, including Random, Selfish, and Queue-aware dispatching.

Performance comparison across multiple metrics.

As shown in the results:

  • Response Time: The MDP policy achieved a 20.67% reduction in average job response time compared to the Queue-aware baseline (97.00 vs. 122.28).
  • Robustness: While traditional "Queue-aware" policies degrade significantly as signaling latency increases—sometimes performing worse than random dispatching due to stale data—the proposed algorithm remains stable.
  • Efficiency: The system maintains a lower average cost and effectively eliminates job dropping, which is a significant issue for "Selfish" policies.

Conclusion and Future Work

This research demonstrates that cooperation in distributed networks can be achieved without a central controller by accounting for the expected behavior of neighboring nodes. While the current model assumes known probability distributions for network latencies, future work could integrate Reinforcement Learning to adapt to dynamic, "black box" environments in real-time.

Summary updated

BibTeX
@inproceedings{hong2020online,
  author = {Yuncong Hong and Bojie Lv and Rui Wang and Haisheng Tan and Zhenhua Han and Hao Zhou and Francis C. M. Lau},
  title = {{Online Distributed Job Dispatching with Outdated and Partially-Observable Information}},
  booktitle = {MSN},
  year = {2020},
  doi = {10.1109/msn50589.2020.00059},
}
Figure