Online distributed job dispatching with outdated and partially-observable information

Hong，Yuncong1,2,3; Lv，Bojie2,4; Wang，Rui2,4; Tan，Haisheng1,4; Han，Zhenhua3; Zhou，Hao1; Lau，Francis C.M.3

10.1109/MSN50589.2020.00059

2020-12-01

978-1-7281-9236-9

Proceedings - 2020 16th International Conference on Mobility, Sensing and Networking, MSN 2020

315-322

17-19 Dec. 2020

Tokyo, Japan

In this paper, we investigate online distributed job dispatching in an edge computing system residing in a Metropolitan Area Network (MAN). Specifically, job dispatchers are implemented on access points (APs) which collect jobs from mobile users and distribute each job to a server at the edge or the cloud. A signaling mechanism with periodic broadcast is introduced to facilitate cooperation among APs. The transmission latency is non-negligible in MAN, which leads to outdated information sharing among APs. Moreover, the fully-observed system state is discouraged as reception of all broadcast is time consuming. Therefore, we formulate the distributed optimization of job dispatching strategies among the APs as a Markov decision process with partial and outdated system state, i.e., partially observable Markov Decision Process (POMDP). The conventional solution for POMDP is impractical due to huge time complexity. We propose a novel low-complexity solution framework for distributed job dispatching, based on which the optimization of job dispatching policy can be decoupled via an alternative policy iteration algorithm, so that the distributed policy iteration of each AP can be made according to partial and outdated observation. A theoretical performance lower bound is proved for our approximate MDP solution. Furthermore, we conduct extensive simulations based on the Google Cluster trace. The evaluation results show that our policy can achieve as high as 20.67% reduction in average job response time compared with heuristic baselines, and our algorithm consistently performs well under various parameter settings.

Metropolitan area networks Markov processes Dispatching Servers Time complexity Optimization Edge computing

通讯

英语

EI ; CPCI-S

WOS:000682965600042

20211710253800

Complex networks ; Iterative methods ; Markov processes ; Optimization ; Petroleum reservoir evaluation ; Wimax

Petroleum Deposits : Development Operations:512.1.2 ; Computer Systems and Equipment:722 ; Optimization Techniques:921.5 ; Numerical Methods:921.6 ; Probability Theory:922.1

2-s2.0-85104606939

Scopus

1.University of Science and Technology of China,LINKE Lab,Hefei,China
2.Southern University of Science and Technology,Department of Electrical and Electronic Engineering,Shenzhen,China
3.The University of Hong Kong,Department of Computer Science,Hong Kong
4.Research Center of Networks and Communications,Peng Cheng Laboratory,Shenzhen,China

Hong，Yuncong,Lv，Bojie,Wang，Rui,et al. Online distributed job dispatching with outdated and partially-observable information[C],2020:315-322.