Undefined Description
Typically, the stream of pods that a cluster is subjected to is heterogeneous with respect to resource (demand) requests. Furthermore, this heterogeneity varies over time. Therefore, the scheduler needs to change its placement policy dynamically in order to accommodate the change in the mixed demand, resulting in lower failure probability and shorter pending times, especially for large pods.
An Adaptive Bin Packing (ABP) algorithm which attempts to equalize measures of variability in the demand and the allocated resources in the cloud, without the need to set any configuration, was recently introduced [1]. Experimental results based on simulations were presented, and the behavior of ABP and its adaptability to the demand mix was demonstrated. It was shown that ABP performs close to the optimized policy, yet evolves to an extreme policy (spread and pack) as the variation in the mix becomes extreme.
Detailed description of the algorithm and simulation experiments are attached tantawi_icac19_slides.pdf
.
We refer to the scheduler plugin implementation of ABP as pigeon, inspired from pigeon holing, where pigeons select holes in a pigeonhole structure in a collective and organized way, in analogy to bin-packing of pods on nodes in a cluster.
Pigeon was implemented as a scheduler extension. Here, we plan to provide an implementation that conforms with the Kubernetes scheduling framework as a scheduler plugin, open-sourced in the sig-scheduling community.
The core ABP algorithm is implemented in C (pigeon_c) and is built as a dynamic library (libpigeon.so) that the pigeon plugin will use.
[1] Tantawi, A. N. and Steinder, M., "Autonomic Cloud Placement of Mixed Workload: An Adaptive Bin Packing Algorithm", IEEE International Conference on Autonomic Computing (ICAC), 2019.