Reinforcement Learning in Computing and Network Convergence Orchestration

For the CNC framework, it has 2 classes of nodes – network nodes and computing nodes. Different nodes have various transmission capacity (e.g. bandwidth) and computation resource (e.g. memory storage, CPU, GPU). However, the computation resource is limited, and the node transmits a limited number of tasks, which is within the transmission capacity, at the same time. If the working condition is over the transmission capacity or the computation resource limit, then the node is considered to be break down, leading to the failure of network system, in this paper. When the network is functional, we call the network is in health condition. It is worth noting that the performance of a node will drop significantly when its workload is very close to its limit. A good orchestration strategy should avoid scenarios that push any node to its limit.

When a task arrives, it will get into the network from the access node (one kind of network node). Then, the orchestration plane will find computing node(s) and path(s) from access node to the computing node(s). The task will send to the destination for processing. Each task will remain for several time slot according to the task requirement, and there could be multiple tasks arrives at the same time slot. Thus, how to make orchestration when the number of tasks in each time slot is large require careful calculation.

There are various kinds of computing nodes. A part of them, such as edge nodes, have low computation resource (weak computing power) and low latency (small transmission delay). On the contrary, another part of computation nodes, like cloud nodes, have rich computation resource (strong computing power) and high latency (long transmission delay). The remaining computation nodes are somewhere between the above two. Furthermore, it is typical that the computation cost is much cheaper at the cloud nodes than that at the edge nodes. For example, the electricity cost of maintaining per unit of computing resource at a cloud center in the west of China is significantly lower than the electricity cost of maintaining per unit of computing resource at a edge in the east of China.

As a result, the advantages of cloud nodes are low cost and fast calculation speed, and its disadvantage is long transmission delay, whilst the strength of edge nodes is low low transmit delay, and its weaknesses are high cost and slow calculation speed. Based on the characteristics of the task, some tasks (e.g. large tasks require intense computation but not sensitive to delay) are better to assign to cloud nodes, whilst others (e.g. small tasks are easy to compute but require low latency) are better to process at the edge nodes.

Recall that CNC can collect information, including CPU usage, bandwidth, upload speed, download speed etc, for each network node and computation node. The orchestration efficiency can be enhanced, if these information are utilized properly during strategizing the computing node and the associated path from access node to the computing node. An orchestration strategy is to determine the optimal computing node as well as the path connecting between the access node and the computing node. As mentioned previously, different types of tasks have their most suitable computing nodes. Therefore, the orchestration strategy must take into account of the the task properties, including the required computation resource, the maximum latency and cost that can tolerate etc. If the selected path meets the task’s requirement, the task is accepted by the system. Otherwise, the task will be rejected by the system. Fig 2 demonstrates an example of CNC orchestration.

To evaluate the orchestration strategy, an objective function (criterion) is required. In particular, the optimal orchestration strategy should optimize the objective function, e.g. maximize the profit, minimize the cost and latency. Given a set of tasks, the optimal orchestration should accept as many tasks as possible and schedule them to the suitable computing nodes so that the accumulated value of objective function (e.g. accumulated profit or accumulated cost) is optimized. Meanwhile, the orchestration strategy should avoid the network break down, which is a devastating destruction for the system. Moreover, it is better to prevent any node from reaching a level close to its workload limit.

In the traditional setting, an amount of revenue will be given when accepting a task. Then, given a set of tasks, an intuitive objective function could be the total profit, which is equal to the sum of the revenues collected minus the sum of the system cost. To address the other factors like latency, one can add the factors as a penalized term to the objective function. The domain of this optimization problem includes the computing nodes and the paths from access nodes to the computing nodes. Since there are a large number of combinations of computing nodes and paths, the domain is large to explore, resulting a complex optimization problem. We will use 4 methods to obtain the orchestration strategy, and evaluate them by the objective function as well as the factors including profit, latency, and decision time.

Suppose a sequence of tasks $\mathbf{M}=(M_{1},\ldots,M_{k})$ waiting for scheduling and orchestration. The current status of all nodes is observed, denoting the status as $\mathcal{S}$. Given a task $M_{i},\ i=1,\ldots,k$, one can search all computing nodes that can meet the task’s requirement. Then, the candidate paths can be found, where candidate paths include all paths from the access node to the computing nodes that does not break down the system. Let $\mathrm{D}$ be the set of all paths in the network, and $\mathcal{D}_{M_{i}}$ be the set of candidate paths that can meet the requirement of $M_{i}$. Then, the profit $p(M_{i})$ for task $M_{i}$ is

where $R_{M_{i}}$ and $C_{M_{i}}$ are revenue and cost, $l^{*}_{M_{i}}$ and $l{M_{i}}$ are the actuarial and required latency respectively. Since reject a task cannot receive any revenue, $R_{M_{i}}=0$ if rejecting task $i$. The cost and actuarial latency vary for different path $d_{i}$. The $(\bullet)^{+}$ is a ReLU (Rectified Linear Unit) function, which is equal to itself only when its value is greater than 0, otherwise is equal to 0.

The orchestration optimization objective is

The remaining of this section introduces 3 methods to determine $d_{i}$.

The random selection includes the following two steps:

• •

  all candidate paths for task $M_{i}$ are searched, consisting the set $\mathcal{D}_{M_{i}}$;

• •

  use random number generator to sample a path $d_{i}$ from $\mathcal{D}_{M_{i}}$.

This two-step process keeps going for all tasks. Eventually, the orchestration strategy for the sequence of tasks are $d_{1},\ldots,d_{k}$. The last node of $d_{i}$ indicates the selected computing node for task $M_{i}$.

It is worth noting random selection does not maximize the profit (objective function), but it is easy for implementation. Also, it can guarantee the system never break down, since all paths are selected from the candidate paths and all nodes’ workload are not over their limits (allow pushing the workload to the limit). Therefore, random selection is a good benchmark for the experiment, which is also the benchmark in [13].

The balanced-resource method includes the following three steps:

• •

  all candidate paths for task $M_{i}$ are searched, consisting the set $\mathcal{D}_{M_{i}}$;

• •

  check the workload of computing nodes in $\mathcal{D}_{M_{i}}$, and the computing node with the lowest workload will be chosen as the computing node for $M_{i}$;

• •

  Once the computing node is fixed, find the best paths $d_{i}$ to the selected computing node in $\mathcal{D}_{M_{i}}$, where the best paths are in terms of the highest available bandwidth and lowest latency.

This three-step process keeps going for all tasks. Eventually, the orchestration strategy for the sequence of tasks are $d_{1},\ldots,d_{k}$.

By doing so, the workloads for computing nodes and network nodes are balanced, under which the network works most efficiently and safely according to experts’ opinion. The system never break down by balanced-resource method since it selects the path with lowest workload. However, this method does not maximize the profit (objective function). This method can be a benchmark from expert experience for the experiment, which is also a benchmark in [13].

The balanced-resource method includes the following three steps:

• •

  all candidate paths for task $M_{i}$ are searched, consisting the set $\mathcal{D}_{M_{i}}$;

• •

  loop through all the paths in $\mathcal{D}_{M_{i}}$, find the best paths $d_{i}$, where the best paths are in terms of the highest profit for current task.

This two-step process keeps going for all tasks. Eventually, the orchestration strategy for the sequence of tasks are $d_{1},\ldots,d_{k}$.

By doing so, each task is assigned to the most profitable path. The system never break down by greedy method since it only choose path from candidate paths. Besides, this method is the intuitive method to maximize the profit (objective function), which is also a benchmark in [14].

This is our proposed method for orchestration. The reinforcement learning method is to train an agent (DQN) that can choose the optimal computing node and path. The input of the DQN is the task’s ($M_{i}$’s) requirement, and the output of the DQN is the optimal path $d_{i}$. More theoretical details on RL are referred to [15]. To illustrate the RL method, we define state $S$, action $A$, reward $R$, and the agent using DQN.
 State $S$: The state consists of all nodes information, including computing resource, current available bandwidth, and CPU processing speed, etc. The state also contains the task requirement like computation resource, bandwidth, latency, as well as task properties such as revenue.
 Action $A$: The action space is the set of all paths $\mathcal{D}$. The agent can choose a path in $\mathcal{D}$ in each action.
 Reward $R$: It is intuitive to set

where $\sum_{i=1}^{k}p(M_{i})$ is the accumulated profit in an episode, and $\delta$ is the penalty term for actions break down the system. When the network is in health condition, $\delta=0$. According to our experiments, $\delta$ cannot be too large. If $\delta$ is too large, the agent likely learns rejecting all tasks for conservative behavior.
 Agent: The agent makes the orchestration strategy. We use DQN to model the agent. Generally, one can apply more sophisticated RL methods, e.g. DDPG (Deep Deterministic Policy Gradient), TRPO (Trust Region Policy Optimization), PGB (Policy Gradient with Baseline). Based on the current state $S$, the agent evaluates the best action $a$ to achieve the highest reward $R$. Before deploying the agent, it needs to be trained by past experience.

To demonstrate the proposed method outperform the other two methods, we conduct simulation experiments based on a virtual network system. The system includes three types of computation nodes to represent the difference between mobile edge computing (MEC), edge cloud, cloud center with different resources capacity and positions in the network topology. We use a typical setup for the network system that has higher delay at nodes with higher loading and the latency between two nodes is determine by their distance.

The tasks’ properties are randomized within certain range for better generalization. For example, some tasks require a lot of computing resource with high latency tolerance, while some tasks require little computing resource but sensitive to latency. And the number of task in each time slot is set differently to test its affection.

It requires to train the agent before testing for RL, while random selection method, balanced-resource method and greedy method can apply directly on testing. The experiment consists of a total of 20,000 tasks for RL training with 10 tasks per time slot and 1000 tasks for testing respectively. Our experiment was conducted by using gym modulo to simulate the environment and using PyTorch to construct and train the agent in Python 3.8.

For random selection method, balanced-resource method and greedy method, the reward is the same as the profit since the available candidate paths will not break the system, and for RL method, the reward is profit with break down penalty $\delta$. We compare the accumulated reward with different task number in each time slot by the four methods in Fig 3 (a), (b) and (c). According to the figure (a), when the task number in each time slot is small, the greedy method generates highest accumulated reward; RL method is the second but very close to the greedy method; balanced-resource method is the third. Here the random selection method generate a negative accumulate rewards after 50 tasks, which is caused by huge latency when used resource is close to the limit. According to the figure (b), when the task number in each time slot is medium, the RL method generates highest accumulated rewards and greedy method is the second even though it achieves the best reward for every task. Here the behavior of random selection method and balanced-resource method are similar to each other, drop done to negative reward. Because when the task number increases, there is no enough resource for all the tasks, thus orchestrating more task into the system will cause the used resource close to the limit, leading to large latency. The reason why RL method is better is because RL agent learns the potential value of each task and reject some low reward task to provide resource to later high reward task. This shows the high accumulated reward advantage of RL is more significant as an increasing number of tasks for orchestration.

To examine the effect of task number in each time slot, we test the performance of all four method with different tasks per time slot. As the figure (c) shows, when the task number is small (1-3), greedy method is the best, balanced-resource method and RL method are second and third respectively. This is when the resource is abundant and far from the resource limit. It is understandable that greedy method is the best orchestration method in this situation. When the task number per time slot is medium (4-24), RL method is the best. This is when the resource is not enough for all the task and used resource is close to the limit. When the task number per time slot is high (25-), RL method is still the best but perform very close to greedy method. This is where the resource is not enough for the tasks in even one time slot. The performance of all four method tend to be stable after more tasks per time slot, the reason is that the extra tasks will just be rejected due to no resources or low reward.

In Fig 3 (c), we compare the average latency of 1000 tasks, which is an important factor for service-level agreement (SLA), by the 4 methods. The average latency by random selection is the highest and balanced-resource method is the second highest, whilst the average latency by greedy method and RL method is far less than the other two methods. The overall latency of RL method is lower than greedy method. Hence, the orchestration by RL is more efficient with lower latency than the other 3 methods.

The average of 1000 tasks’ decision time, see table II, that is the time required to obtain 1000 optimal path, is 0.04s by RL method. Compared with the 0.49 ms and 0.46 ms by balanced-resource method and greedy method, the decision time reduces 90%, which shows orchestration by RL is more efficient than that by greedy method and balanced-resource method with respect to the time required for orchestration. The decision time of random selection is still the shortest, 0.01s. Recall that the network topology in our experiment is a simple version of that in real-world, the advantage of decision speed by RL is more meaningful in real network applications.

In this paper, we demonstrated the proposed RL method is applicable for CNC orchestration. Compared with the traditional method using the random selection, balanced-resource method and greedy method, the RL method improves the network efficiency with lower latency, lower decision time, and higher accumulated profit. The trained agent by RL can learn to select the optimal computing nodes for tasks based on the tasks’ characteristics and reject tasks when the resources is full. The agent takes into account of reserving resources for future tasks, e.g. the resource is reserved for more profitable tasks in our experiment.

Additionally, the trained agent is easy to deploy in orchestration control plane. It has great value to apply RL on the CNC orchestration.

The RL method requires model training before deploying. It is challenging to train the agent when the network topology is complicated. Unfortunately, the network topology in real world is complicated. In order to over this challenge, some pre-processing, e.g. simplify the network topology by grouping network nodes based on experts’ experience, may be needed.

The second challenge is how to mimic the network in real world as accurate as possible in the simulation environment. To fill the gap of simulation accuracy, it involves a lot of expert experience as well as advance technologies, such as machine learning methods, to refine the network simulator.