Mathematically formulating formal problem of a cloud service scheduler

Question

So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to do, which is why I am unsure of how to proceed with it.

I guess, first logical thing to do, is to explain, what is a scheduler's problem. Well, generally, we have two classes:

• Nodes, which have some predetermined amount of resources;
• Pods, which, while while active, consume resources.

Pods become active, when they are assigned to a node and they exist for a while, until they are either completed, expired (failed to complete over a long time), or until they are brought down to be assigned to a different node. The latter can happen when a new pod is added by the system and the system needs to rearrange some already existing pods to fit in a new one. This can also occur if the pod suddenly demands more resources than it was expected to.

Another important detail is, when a pod is being set, the node it is being set to, tries to guess, how many resources to reserve for this pod. Reserved resources are for a specific pod only. Not only that, a pod cannot use resources that were not assigned to it. The only way to reassign resources to a pod, is to kill it and recreate it (possibly on another node) with new assigned resources to it.

Some other rules of the game:

• several pods can be assigned to one node
• several nodes cannot share one pod
• resources we are talking about are not consumables — once a pod no longer exists, resources are returned to node

Knowing that, I tried to formulate the problem on pods level and it goes like this:

$(node - assigned_i - |assigned_i - used_t| - i \cdot w_i) \to maximize$, where

• $node$ — resources that were not occupied in a node
• $assigned_i$ — resources that scheduler chose to assign to the pod. It is marked with underscored i, because scheduler can also reassign resources, so there might be several instances of it.
• $used_t$ — resources used at the time t. I believe we have to measure effectiveness of the scheduler in real time, so these are some chaotic time series. I honestly don't know if these are possible to classify
• $w_i$ is some constant that is here to penalize scheduler for reassigning resources, since killing a pod and recreating it is, well, costly on the resources part

At the end we have a model that tries to assign as little resources as possible and gets penalised if it guesses wrongly in any direction, as well as it gets penalized if its guess is wrong to the point it has to kill and restore a pod.

So, is this somewhat closely resembling the real problem? What are possible ways I can take this problem to nodes scale? I also might be missing something...

UPD: I guess there should be individual layers of problem for a node and for the scheduling system as a whole. What changes for individual node level, is that all variables, except $node$ become vectors (as there are typically several pods assigned to one node). This said,I do not understand how to mathematically show that $node$ is determined by all pods resource assignment simultaneously. That is, if we assign $assigned_1$ resources to some pod, it leaves just $node - assigned_1$ resources for the rest of the pods assigned to this node.

Moreover, I am completely lost on how to formulate this on the scale of the scheduling system.

Answer 1

So, in case anyone is wondering, I actually figured the solution on my own. I ended up using constraint programming. For the sake of plagiarism check in my university, I am to say that this formulation was designed for «Playing the Dispatcher» project from 1C.

$\mathcal{X} = \{max_i, a_j, u_t, r_j, p, w_j, x_{ij}\}$ — set of variables.

$max_i = \begin{bmatrix} memory_i\\cpu_i \end{bmatrix}, \space \forall i \in \mathbb{N}$ — all the resources an ith node can offer.

$a_j = \begin{bmatrix} memory_j\\cpu_j \end{bmatrix}, \space \forall j \in \mathbb{N}$ — the resources assigned to a jth pod.

$u_t = \begin{bmatrix} memory_t\\cpu_t \end{bmatrix}, \space \forall t \in \mathbb{N}$ — resources used at a specific period of time t, typically calculated in seconds / minutes / frames. Is a chaotic time series bounded by computational constraints.

$r_j, \space \forall j \in \mathbb{N}$ — some constant that is brought to punish process reassignment, $r_j = n \cdot c$, where $n$ is the number of times a jth pod got reassigned and $c$ is a modifier.

$p_t, \space \forall t \in \mathbb{N}$ — amount of pods requested to be processed at a time t.

$w_j, \space \forall j \in \mathbb{N}$ — weight assigned to a pod by scheduler.

$x_{ij} = 1, \space \forall i \forall j \in \mathbb{N}$ if jth pod was assigned to ith node and 0 otherwise.

$\mathcal{D} = \{D_{max}, D_a, D_u, D_r, D_p, D_w, D_x\}$ — set of domains of variables.

$D_{max}, D_a, D_u \in \mathbb{N}^2$

$D_r \in \mathbb{R}$

$D_p, D_w \in \mathbb{N}$

$D_x \in \{0, 1\}$

And the set of constraints and functionals:

$\mathcal{C} = \{C_0, C_1 \}$

$C_0: \space (max - a_j - |a_j - u_t| - r_j) \cdot (\sum_{j=1}^{p_t} (w_j \cdot x_{ij}) \cdot f(x)) \to maximize$

$C_1: \space max_i - \sum_{j = 1}^{p_t} a_j \geq 0$

$f(x) = 100 - g(x)$, $g(x)$ — uneven distribution of resources. $D(g) \in [0, 100)$ and $g(x) \in \mathbb{R}$