4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to OR SE. The first thing to do, in my opinion, is to decide whether you want to model this as a mixed-integer program (MIP, which fits your choice of tags) or a constraint programming (CP) problem. Either way works, but CP can be more efficient to solve than MIP when dealing with scheduling problems with resource allocations. There is a standard mathematical notation for MIP models. I don't think there is a standard notation for CP models. $\endgroup$
    – prubin
    Mar 23 at 17:43
  • 2
    $\begingroup$ Either way, the next thing to do is settle on an objective function. Minimizing unused resources would be unusual, given that the resources are not consumed. Other possible objectives include minimizing the number of pods not scheduled (if the system is overloaded), minimizing the number of pods that complete late (or their total tardiness) if pods have due dates, minimizing the amount of switching (moving pods between resources), or minimizing waiting time (difference between arrival of pod and time pod gets assigned to a resource). $\endgroup$
    – prubin
    Mar 23 at 17:45

1 Answer 1

3
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.