  Kubernetes (k8s) has the potential to coordinate distributed edge resources
and centralized cloud resources, but currently lacks a specialized scheduling
framework for edge-cloud networks. Besides, the hierarchical distribution of
heterogeneous resources makes the modeling and scheduling of k8s-oriented
edge-cloud network particularly challenging. In this paper, we introduce KaiS,
a learning-based scheduling framework for such edge-cloud network to improve
the long-term throughput rate of request processing. First, we design a
coordinated multi-agent actor-critic algorithm to cater to decentralized
request dispatch and dynamic dispatch spaces within the edge cluster. Second,
for diverse system scales and structures, we use graph neural networks to embed
system state information, and combine the embedding results with multiple
policy networks to reduce the orchestration dimensionality by stepwise
scheduling. Finally, we adopt a two-time-scale scheduling mechanism to
harmonize request dispatch and service orchestration, and present the
implementation design of deploying the above algorithms compatible with native
k8s components. Experiments using real workload traces show that KaiS can
successfully learn appropriate scheduling policies, irrespective of request
arrival patterns and system scales. Moreover, KaiS can enhance the average
system throughput rate by 15.9% while reducing scheduling cost by 38.4%
compared to baselines.
