1
$\begingroup$

I need to optimize the end-to-end latency of a multi-component application.

Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 components. Note device 1 has cpu limitation and device 2 has unlimited cpu.

The end-to-end latency is calculated by the execution time of 1-5 component + the output data transfer time of component 5 ( to be fed as input to the component 6 (on device 2)) + the execution time of component 6-10.

Due to some system load on device 1, the allocation needs to be changed for instance component 1-3 on device 1 and component 4-10 on device 2 but this allocation must consider the bandwidth constraint and cpu limitation of device1.

I would like to ask can this problem be considered multiobjective or not?.I need to use a multiobjective algorithm to solve the below problem such as pareto optimality or genetic algorithm. The end to end latency is affected by the bandwidth (bandwidth constraint) and device 1 cpu limitation (device1 constraint).

Help is highly appreciated. Thanks.

$\endgroup$
  • $\begingroup$ Did you thougth to introduce 20 binary variables and write an Integer Linear Porgramm model? $ x_{i,j} $ could be a Boolean variable whose value is 1 if i-th component is assigned to j-th training device, 0 otherwise where $i=1,2, \cdots, 10 $ and $i=1,2$. $\endgroup$ – marco tognoli Sep 20 at 8:50
  • $\begingroup$ @marcotognoli thank you very much for your response. Would you please elaborate more on modeling this problem as a linear programming model. Thanks $\endgroup$ – user1566490 Sep 20 at 11:44
  • $\begingroup$ I have just written the more general model. As you can see it is not necessary to consider a multiobjective model because you can easily consider only one single objective function. $\endgroup$ – marco tognoli Sep 20 at 20:05
2
$\begingroup$

Model without bandwidth limitation

We wish to select the most performing components to be hosted by two devices in order to have an end-to-end latency as minimum as possible.

Let $ x_{i,j} $ be a Boolean variable whose value is 1 if i-th component is assigned to j-th device, 0 otherwise where $i=1,2, \cdots, 10 $ and $i=1,2$. The cpu limitation (equals to $c_1$) constraint could be written as

$ \sum_{i=1}^{10} x_{i,1} \leq c_1 $

In order to allocate every component only in 1 and only 1 device and not have a trivial solution (i.e. all variables equal to zero), we can impose that

$ \sum_{j=1}^2 x_{i,j} = 1 $ for every $i=1,\cdots , 10$

The following constraint

$ \sum_{i=1}^{10} x_{i,1} \geq 1 $

requires that at least one component is hosted by device 1 and

$ \sum_{i=1}^{10} x_{i,2} \geq 1 $

the same for device 2.

Let $t_i$ be the execution time of components and $T_i$ the output data transfer time of component i from 1st device to 2nd device. The obijective function Z to be minimized could be

$ Z = ( \sum_{j=1}^2 \sum_{i=1}^{10} t_i \cdot x_{i,j} ) + T $

where $T$ should designate the output data transfer time of i-th component in last position on board of device 1. Because we do not consider bandwidth limitation, $T$ will be equal to 0.

Model with bandwidth limitation

Let $b_i$ be the bandwidth of every components, we have to consider the bandwidth contraint applied only on the “last” component on board of 1st device. This point requires to consider auxiliary variables indicating the ranking of the components on board of device 1 and furnishing the output data transfer time $T$. Because the output data transfer time $T$ is inversely proportional to $b_i$, as last component on device 1 we wish to select the largest available bandwidth. Let introduce ten Boolean auxiliary variables, $ z_1, \cdots, z_{10} $, assuming value is 1 if i-th component transmits bytes from device 1 to device 2. Because only one component is designate to transmit from device 1 to device 2, we introduce the constraint $\sum_{i=1}^{10} z_i = 1$.

$ \min T $

$\left\{ \begin{array}{l} T \geq \sum_{i=1}^{10} b^{-1}_i \cdot z_i \\ x_{1,2} + z_1 \leq 1 \\ x_{2,2} + z_2 \leq 1 \\ \vdots \\ x_{10,2} + z_{10} \leq 1 \\ \sum_{i=1}^{10} z_i = 1 \\ T \geq 0 \\ z_1, \cdots, z_{10} binary \\ \end{array} \right. $

The logic constraint $x_{i,2} + z_i \leq 1$ guarantees to avoid to select components that are allocated on device 2: $x_{i,2}=1 \implies z_i=0$.

Finally, the model is:

$ Z = ( \sum_{j=1}^2 \sum_{i=1}^{10} t_i \cdot x_{i,j} ) + T $

s.t.

$\left\{ \begin{array}{l} T \geq \sum_{i=1}^{10} b^{-1}_i \cdot z_i \\ \sum_{i=1}^{10} x_{i,1} \leq c_1 \\ \sum_{j=1}^2 x_{1,j} = 1 \\ \vdots \\ \sum_{j=1}^2 x_{10,j} = 1 \\ \sum_{i=1}^{10} x_{i,1} \geq 1 \\ \sum_{i=1}^{10} x_{i,2} \geq 1 \\ x_{1,2} + z_1 \leq 1 \\ x_{2,2} + z_2 \leq 1 \\ \vdots \\ x_{10,2} + z_{10} \leq 1 \\ \sum_{i=1}^{10} z_i = 1 \\ T \geq 0 \\ z_1, \cdots, z_{10},x_{1,1}, \cdots, x_{2,10} binary \\ \end{array} \right. $

| improve this answer | |
$\endgroup$
2
$\begingroup$

You can treat it as multiobjective if you treat end-to-end latency as one objective (to be minimized) and load on device 1 (which has limited capacity) as another objective (also to be minimized).

| improve this answer | |
$\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.