Task-Aware Flow Scheduling with Heterogeneous Utility Characteristics for Data Center Networks

We can solve Formula (14) by using the Lagrange multiplier method and KKT condition. The Lagrange function that corresponds to the original problem can be expressed as

(15) $$\text{Lagrange}\left(\begin{array}{cc}{r}_k;{\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_M;\hfill & \\ {\beta }_1,{\beta }_2,\mathrm{\dots },{\beta }_M,\hfill & \\ {\gamma }_1,{\gamma }_2,\mathrm{\dots },{\gamma }_K;\hfill & \\ {\delta }_1,{\delta }_2,\mathrm{\dots },{\delta }_K\hfill & \end{array}\right)=$$ $$\mathrm{\hspace{1em}}{\displaystyle \underset{k=1}{\overset{K}{\sum }}}\ln \left[f_k(r_k)-f_k^0\right]-{\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\alpha }_m{\phi }_1-{\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\beta }_m{\phi }_2+$$ $$\mathrm{\hspace{1em}}{\displaystyle \underset{k=1}{\overset{K}{\sum }}}{\gamma }_k\times (r_k-L_k)-{\displaystyle \underset{k=1}{\overset{K}{\sum }}}{\delta }_k\times (r_k-U_k)$$

The calculation formulas for ${\phi }_1$ and ${\phi }_2$ are as follows:

(16) $${\phi }_1=\underset{i=1}{\overset{N}{\sum }}{\text{loc}}_{i,m}\times \left(\underset{k=1}{\overset{M}{\sum }}\underset{j=1}{\overset{N}{\sum }}\frac{s_k^{i,j}}{s_k}\times r_k\right)-C$$

(17) $${\phi }_2=\underset{i=1}{\overset{N}{\sum }}{\text{loc}}_{i,m}\times \left(\underset{k=1}{\overset{M}{\sum }}\underset{j=1}{\overset{N}{\sum }}\frac{s_k^{j,i}}{s_k}\times r_k\right)-C$$

According to KKT condition, to solve the original problem, we only need to solve the following equations:

(18) $$\{\begin{array}{cc}{\alpha }_m\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\text{loc}}_{i,m}\left({\displaystyle \underset{k=1}{\overset{M}{\sum }}}{\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \frac{s_k^{i,j}}{s_k}}{r}_k\right)-C\right]=0,\hfill & \\ m\in \{1,2,\mathrm{\dots },M\};\hfill & \\ {\gamma }_k\times (r_k-L_k)=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\displaystyle \frac{\partial \text{Lagrange}(\cdot )}{\partial r_k}}=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\delta }_k\times (r_k-U_k)=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\beta }_m\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\text{loc}}_{i,m}\left({\displaystyle \underset{k=1}{\overset{M}{\sum }}}{\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \frac{s_k^{j,i}}{s_k}}{r}_k\right)-C\right]=0,\hfill & \\ m\in \{1,2,\mathrm{\dots },M\}\hfill & \end{array}$$

The solution problem of the above equations is a convex optimization problem with $2M+3K$ constraints. The complexity of the solution increases significantly with the increase in the cluster size and the number of tasks. Therefore, this paper will use a heuristic algorithm to solve the original problem.

The objective of this paper is to optimize system bandwidth resource utility as much as possible while guaranteeing fairness among tasks. For ${\text{task}}_k$ , suppose its maximum utility value is $f_k^{\max }$ (which can be calculated according to utility function), and the actual utility finally achieved is $f_k$ . Then, the utility completion rate for defining ${\text{task}}_k$ is

(19) $${\text{ucr}}_k=f_k/f_k^{\max }$$

This paper uses the well-known Gini coefficient and Lorenz curve^{[ 28 ]} in the field of economics to measure the fairness of utilities among tasks. In economics, the Lorenz curve is used to describe the unfairness of social wealth distribution. The abscissa indicates the accumulation of the proportion of population, the ordinate indicates the accumulation of the proportion of wealth, the 45-degree line indicates the absolute fair distribution of wealth, and the curve formed by the horizontal axis and the right straight line represents the absolute unfair distribution of wealth, while the arc in the middle is for the Lorenz curve. Close proximity of the arc to the 45-degree line corresponds to fair distribution of wealth. Let the area between the Lorentz curve and the 45-degree line be $A$ and the area between the absolute unfair line and the absolute unfair line be $B.$ Then, the ratio of the Gini coefficient to $A$ and $(A+B)$ is defined to measure the unfairness of the distribution of wealth. In this paper, we use the cumulative proportion of tasks as the horizontal axis and the cumulative ratio of utility completion rates as the vertical axis, so that the Lorentz curve and the Gini coefficient are applied to the measurement of the fairness of utilities among tasks.

To optimize system bandwidth resource utilities while guaranteeing fairness among tasks, this paper proposes two utility-aware task bandwidth allocation algorithms to solve the original problem. In accordance with the support function and network conditions of systems, we provide two bandwidth allocation algorithms: non-blocking utility-aware task bandwidth allocation algorithm and blocking utility-aware task bandwidth allocation algorithm.

Non-blocking mode. The detailed process of the algorithm is shown in Algorithm 1. The algorithm is mainly divided into two steps: (1) With the utility proportional attenuation factor $\theta \in (0,1)$ being set, we attempt to ensure that all tasks to reach $f_k^{\max }$ . If not, then we use $(1-\theta )\times f_k^{\max },{(1-\theta )}^2\times f_k^{\max },\mathrm{\dots }$ , to attenuate the utility of each task. The bandwidth allocated for each task is calculated based on the attenuated task utility, and whether the currently allocated bandwidth meets the access link bandwidth capacity constraint is determined; (2) In the case of satisfying the access link bandwidth capacity constraint, the remaining bandwidth is allocated to the task with the largest unit bandwidth utility to maximize the system bandwidth resource utility.

Blocking mode. In the non-blocking utility-aware task bandwidth allocation algorithm, the arriving tasks do not need to wait, and all tasks in the system allocate bandwidth proportionally according to the task scheduling algorithm. When the number of concurrent tasks in the system exceeds the tolerance of the access link, the bandwidth allocated to each task in the system is too small, the task completion time is too long, and the task cannot even be completed within an acceptable time range, thereby resulting in performance degradation or even system crash. We adopt a strategy of controlling the number of concurrent tasks, setting the task concurrent limit, and queuing the tasks in the system that exceed the concurrent limit for service. The detailed process of the algorithm is shown in Algorithm 2. The algorithm is mainly divided into four steps: (1) First, a task concurrent limit maxTask is set. When a task arrives, maxTask performs a self-decreasing operation. If maxTask is reduced to 0, then the subsequent tasks are queued for service. (2) Second, by setting utility proportional attenuation factor $\theta \in (0,1)$ , we attempt to ensure that all tasks reach $f_k^{\max }$ . If not, then we use $(1-\theta )\times f_k^{\max },{(1-\theta )}^2\times f_k^{\max },\mathrm{\dots }$ , to attenuate the utility of each task. The bandwidth allocated for each task is calculated based on the attenuated task utility, and whether the currently allocated bandwidth meets the access link bandwidth capacity constraint is determined. (3) In the case of satisfying the access link bandwidth capacity constraint, the remaining bandwidth is allocated to the task with the largest unit bandwidth utility to maximize the system bandwidth resource utility. (4) When a task is completed, it performs an auto-increment operation on maxTask, so that subsequent tasks waiting for service can be scheduled. Therefore, in the case of an extremely congested system network, Algorithm 2 implements the control of concurrent tasks number in the system and improves the performance of the system in handling network congestion.

We can solve Formula (14) by using the Lagrange multiplier method and KKT condition. The Lagrange function that corresponds to the original problem can be expressed as

(15) $$\text{Lagrange}\left(\begin{array}{cc}{r}_k;{\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_M;\hfill & \\ {\beta }_1,{\beta }_2,\mathrm{\dots },{\beta }_M,\hfill & \\ {\gamma }_1,{\gamma }_2,\mathrm{\dots },{\gamma }_K;\hfill & \\ {\delta }_1,{\delta }_2,\mathrm{\dots },{\delta }_K\hfill & \end{array}\right)=$$ $$\mathrm{\hspace{1em}}{\displaystyle \underset{k=1}{\overset{K}{\sum }}}\ln \left[f_k(r_k)-f_k^0\right]-{\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\alpha }_m{\phi }_1-{\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\beta }_m{\phi }_2+$$ $$\mathrm{\hspace{1em}}{\displaystyle \underset{k=1}{\overset{K}{\sum }}}{\gamma }_k\times (r_k-L_k)-{\displaystyle \underset{k=1}{\overset{K}{\sum }}}{\delta }_k\times (r_k-U_k)$$

The calculation formulas for ${\phi }_1$ and ${\phi }_2$ are as follows:

(16) $${\phi }_1=\underset{i=1}{\overset{N}{\sum }}{\text{loc}}_{i,m}\times \left(\underset{k=1}{\overset{M}{\sum }}\underset{j=1}{\overset{N}{\sum }}\frac{s_k^{i,j}}{s_k}\times r_k\right)-C$$

(17) $${\phi }_2=\underset{i=1}{\overset{N}{\sum }}{\text{loc}}_{i,m}\times \left(\underset{k=1}{\overset{M}{\sum }}\underset{j=1}{\overset{N}{\sum }}\frac{s_k^{j,i}}{s_k}\times r_k\right)-C$$

According to KKT condition, to solve the original problem, we only need to solve the following equations:

(18) $$\{\begin{array}{cc}{\alpha }_m\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\text{loc}}_{i,m}\left({\displaystyle \underset{k=1}{\overset{M}{\sum }}}{\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \frac{s_k^{i,j}}{s_k}}{r}_k\right)-C\right]=0,\hfill & \\ m\in \{1,2,\mathrm{\dots },M\};\hfill & \\ {\gamma }_k\times (r_k-L_k)=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\displaystyle \frac{\partial \text{Lagrange}(\cdot )}{\partial r_k}}=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\delta }_k\times (r_k-U_k)=0,k\in \{1,2,\mathrm{\dots },K\};\hfill & \\ {\beta }_m\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\text{loc}}_{i,m}\left({\displaystyle \underset{k=1}{\overset{M}{\sum }}}{\displaystyle \underset{j=1}{\overset{N}{\sum }}}{\displaystyle \frac{s_k^{j,i}}{s_k}}{r}_k\right)-C\right]=0,\hfill & \\ m\in \{1,2,\mathrm{\dots },M\}\hfill & \end{array}$$

The solution problem of the above equations is a convex optimization problem with $2M+3K$ constraints. The complexity of the solution increases significantly with the increase in the cluster size and the number of tasks. Therefore, this paper will use a heuristic algorithm to solve the original problem.

The objective of this paper is to optimize system bandwidth resource utility as much as possible while guaranteeing fairness among tasks. For ${\text{task}}_k$ , suppose its maximum utility value is $f_k^{\max }$ (which can be calculated according to utility function), and the actual utility finally achieved is $f_k$ . Then, the utility completion rate for defining ${\text{task}}_k$ is

(19) $${\text{ucr}}_k=f_k/f_k^{\max }$$

This paper uses the well-known Gini coefficient and Lorenz curve^{[ 28 ]} in the field of economics to measure the fairness of utilities among tasks. In economics, the Lorenz curve is used to describe the unfairness of social wealth distribution. The abscissa indicates the accumulation of the proportion of population, the ordinate indicates the accumulation of the proportion of wealth, the 45-degree line indicates the absolute fair distribution of wealth, and the curve formed by the horizontal axis and the right straight line represents the absolute unfair distribution of wealth, while the arc in the middle is for the Lorenz curve. Close proximity of the arc to the 45-degree line corresponds to fair distribution of wealth. Let the area between the Lorentz curve and the 45-degree line be $A$ and the area between the absolute unfair line and the absolute unfair line be $B.$ Then, the ratio of the Gini coefficient to $A$ and $(A+B)$ is defined to measure the unfairness of the distribution of wealth. In this paper, we use the cumulative proportion of tasks as the horizontal axis and the cumulative ratio of utility completion rates as the vertical axis, so that the Lorentz curve and the Gini coefficient are applied to the measurement of the fairness of utilities among tasks.

To optimize system bandwidth resource utilities while guaranteeing fairness among tasks, this paper proposes two utility-aware task bandwidth allocation algorithms to solve the original problem. In accordance with the support function and network conditions of systems, we provide two bandwidth allocation algorithms: non-blocking utility-aware task bandwidth allocation algorithm and blocking utility-aware task bandwidth allocation algorithm.

Non-blocking mode. The detailed process of the algorithm is shown in Algorithm 1. The algorithm is mainly divided into two steps: (1) With the utility proportional attenuation factor $\theta \in (0,1)$ being set, we attempt to ensure that all tasks to reach $f_k^{\max }$ . If not, then we use $(1-\theta )\times f_k^{\max },{(1-\theta )}^2\times f_k^{\max },\mathrm{\dots }$ , to attenuate the utility of each task. The bandwidth allocated for each task is calculated based on the attenuated task utility, and whether the currently allocated bandwidth meets the access link bandwidth capacity constraint is determined; (2) In the case of satisfying the access link bandwidth capacity constraint, the remaining bandwidth is allocated to the task with the largest unit bandwidth utility to maximize the system bandwidth resource utility.

Blocking mode. In the non-blocking utility-aware task bandwidth allocation algorithm, the arriving tasks do not need to wait, and all tasks in the system allocate bandwidth proportionally according to the task scheduling algorithm. When the number of concurrent tasks in the system exceeds the tolerance of the access link, the bandwidth allocated to each task in the system is too small, the task completion time is too long, and the task cannot even be completed within an acceptable time range, thereby resulting in performance degradation or even system crash. We adopt a strategy of controlling the number of concurrent tasks, setting the task concurrent limit, and queuing the tasks in the system that exceed the concurrent limit for service. The detailed process of the algorithm is shown in Algorithm 2. The algorithm is mainly divided into four steps: (1) First, a task concurrent limit maxTask is set. When a task arrives, maxTask performs a self-decreasing operation. If maxTask is reduced to 0, then the subsequent tasks are queued for service. (2) Second, by setting utility proportional attenuation factor $\theta \in (0,1)$ , we attempt to ensure that all tasks reach $f_k^{\max }$ . If not, then we use $(1-\theta )\times f_k^{\max },{(1-\theta )}^2\times f_k^{\max },\mathrm{\dots }$ , to attenuate the utility of each task. The bandwidth allocated for each task is calculated based on the attenuated task utility, and whether the currently allocated bandwidth meets the access link bandwidth capacity constraint is determined. (3) In the case of satisfying the access link bandwidth capacity constraint, the remaining bandwidth is allocated to the task with the largest unit bandwidth utility to maximize the system bandwidth resource utility. (4) When a task is completed, it performs an auto-increment operation on maxTask, so that subsequent tasks waiting for service can be scheduled. Therefore, in the case of an extremely congested system network, Algorithm 2 implements the control of concurrent tasks number in the system and improves the performance of the system in handling network congestion.