RISA: Round-Robin Intra-Rack Friendly Scheduling Algorithm for Disaggregated Datacenters

The disaggregated datacenter architecture proposed in (Zervas et al., 2018) is used as the case study in this work (see Figure 3). This architecture is structured into racks. Within each rack, there are several boxes, each box has some amount of a single resource type: CPU, RAM, or storage. These boxes are further divided into bricks, with each brick holding a predetermined quantity of its designated resource. Each box is equipped with optical switches, connected to rack-level switches, for communication. Progressing up the hierarchy, rack switches then connect to inter-rack switches. As seen in Figure 2, if a CPU brick within a CPU box in rack 0 intends to interact with a RAM brick within a RAM box in rack 1, the communication journey would entail traversing the box switch of rack 0, its rack switch, the inter-rack switch, the switch of rack 1, and finally, the RAM box’s switch before reaching its destination.

Table 1 offers a detailed configuration utilized in our simulation study. Notably, within a brick, all communication is electronic. Once the data leaves the brick, it gets converted from electronic to photonic by a single-mode Luxtera commercial SiP optical module (Luxtera, 2023) (depicted in Figure 3). This module uses eight spatially multiplexed optical channels, each capable of supporting a 25Gb/s bit rate, for a total of 200Gb/s per link. Utilizing transceivers that operate in single-mode, rather than multimode, enables a more scalable network built on optical circuit switching (OCS). This is because single-mode fibers accommodate optical switches with a greater number of ports (Nagashima et al., 2016). We obtain the power consumption of the transceiver module to be 22.5 $pJ/bit$ from (Zervas et al., 2018). Using Tables 1 and 2 (Zervas et al., 2018), we can get a sense of network requirements for different sizes of VMs.

To accurately model the optical switch power, we need to consider the states of the cells within a switch. Known for their fast reconfiguration times, we consider microring resonator (MRR)-based switches for our disaggregated setup. For the switch configuration, we selected a commonly used Beneš network configuration.

Within an optical switch, ports are interconnected through a network of cells. Each cell in the switch can be in either “cross” or “bar” state. When a VM requests a path through a switch, some cells must change their states. For this, each of these cells consumes switching power ($P_{swcell}$). Thus, if there are $n$ number of cells along a switch path, we assume that $n/2$ of the cells will undergo reconfiguration. For the rest of the time, to maintain a cell’s state it consumes trimming power ($P_{trimcell}$). Therefore, the optical switch energy consumed for each VM ($E_{sw}$) is:

where $lat_{sw}$ is the latency of switching the cells (dependent on the switch size (De Magalhães et al., 2021)), $\alpha$ is a constant to consider the fact that two VMs can share the same cell, and $T$ is the lifetime of the VM.

Based on the findings in (Mirza et al., 2022), we considered $P_{trimcell}=22.67mW$ and $P_{swcell}=13.75mW$. The number of cells in a Beneš-based optical switch is dependent on the number of ports on the switch, as detailed in (Lee and Dupuis, 2019). Similarly, the latency of switching the cells are also based on the switch size (De Magalhães et al., 2021). The switch configurations are detailed in the experimental results in Section 5. Since two VMs can share the same switch cell $\alpha$ should be between $0.5$ (every cell is shared) and $1$ (no cell is shared). For the purpose of our simulations, we’ve chosen the value of $\alpha$ to be $0.9$.

Figure 4 shows a generic view of an optical switch, represented by the largest box. The boxes inside the switch with solid outlines represent the cells that are being utilized (dashed are inactive). In the figure, we show two paths, $P1$ and $P2$, corresponding to two VMs that share an MRR cell.

Before discussing RISA in detail, it’s crucial to first grasp the workings and limitations of NULB and NALB. Both of these algorithms have a compute (CPU/RAM/storage) resource allocation phase and a network resource allocation phase.

During the compute resource allocation phase, (Zervas et al., 2018) prioritizes the most scarce resource by examining the contention ratio (CR) or the amount of a resource required by a VM over the total amount of that available resource. NULB and NALB both first search for a suitable box to satisfy the resource request with the highest CR. Then, NULB searches for the other resources using breadth-first search (BFS), while NALB uses a modified BFS. In modified BFS, NALB reorders neighbors of the scarce resource in descending order of their available bandwidth. In the network resource allocation phase, NULB selects the first available link to establish the connection between each pair of resources. NALB chooses links with the most available bandwidth.

The way the compute resource search is prioritized in NULB or NALB, it encourages inter-rack network utilization. Thus, even though the network allocation phase of NALB is network-aware, it does not truly discourage higher network utilization.

To better assign VMs to intra-rack resources, RISA keeps track of the boxes with the maximum amount of each resource for each rack. Thus, when a VM requests resources, we can easily determine which racks have boxes that can accommodate the entire VM. These racks that can house the entire VM are placed in a list called $INTRA\_RACK\_POOL$. To help balance the load between racks, we adopt a round-robin policy for selecting racks from $INTRA\_RACK\_POOL$. This helps to make the utilization of the racks more uniform. Algorithm 1 details the different steps of RISA. $REQ$ indicates the VM compute requirements. $NET$ indicates the total network bandwidth available. $AVAIL\_INTRA\_RACK\_NET$ indicates the total intra-rack network bandwidth available.

If INTRA_RACK_POOL is empty or available intra-rack network resources is insufficient to schedule a VM using INTRA_RACK_POOL, we create three lists, known as the $SUPER\_RACK$ collectively. Within the $SUPER\_RACK$, each list contains the racks with boxes with sufficient resources (CPU or RAM or storage) for a VM assignment. In such a scenario, the VM assignment has to be inter-rack. In this case, RISA resorts to NULB (Zervas et al., 2018) (Algorithm 2) to perform the VM allocation. The choice boxes for VM assignment are then limited to the boxes of racks within the SUPER_RACK. Also, VM assignment starts with first finding the most contended resource, then based on BFS, other resources are first searched for in the same rack and then searched for in other racks.

Algorithm 2 outlines the different steps of NULB. $res\_type$ indicates all kinds of resources (e.g., CPU, RAM, and storage). After finding the most scarce resource, $res_{max}$ using CR, NULB first looks for the first box with the available $res_{max}$ requested by a VM. Next, using BFS, NALB first looks for other requested resources by VM in the same rack. If it doesn’t find them in the same rack it looks for resources in other racks. Once a set of boxes with available resources is found, this indicates successful completion of the compute allocation phase. Next, NALB checks to see if the available network bandwidth is present in the connecting optical links. If it finds the links with the necessary bandwidth, the VM assignment is successful with the completion of the network allocation phase. If either the compute allocation or network allocation fails, the VM to be assigned is dropped.

In line with traditional VM scheduling algorithms promoting the best-fit packing, we investigate a variant of RISA, RISA-BF, prioritize boxes with lower available resources when INTRA_RACK_POOL is not empty. The main goal for RISA-BF is to better pack resources and reduce resource stranding. The resulting algorithm can be seen in Algorithm 3 and has been shown to have superior results when compared to the RISA.

In this section, we will see scenarios where RISA will outperform NULB and NALB. We will also see how RISA-BF may outperform RISA.

We will now see how NULB, NALB, RISA, and RISA-BF schedule a synthetic random workload on our disaggregated architecture discussed in Section 3. We generated a random workload similar to the synthetic random workload in (Zervas et al., 2018). A VM can have a random amount of CPU cores from 1 to 32 cores and a random amount of RAM from 1 to 32 GB. Storage for every VM is 128 GB. Requests are produced dynamically based on a Poisson distribution with a mean interarrival period of 10 time units. The VM life cycle begins at 6300 time units, with an increment of 360-time units for each set of 100 requests. A total of 2500 VMs were generated.

The average CPU utilization for all algorithms was $64.66\%$, the average RAM utilization for algorithms was $65.11\%$ and the average storage utilization for algorithms was $31.72\%$. As seen in Figure 5, despite utilizations well below $100\%$, both NULB and NALB had 255 inter-rack VM assignments. On the other hand, RISA and RISA-BF had only 7 and 2 inter-rack VM assignments respectively.

We will now compare the performance of the algorithms in the areas of network utilization, energy consumption, and average CPU-RAM latency using the 2017 public release of Microsoft Azure data center traces (Cortez et al., 2017). To choose workloads of different characteristics, we selected different subsets of the 2017 Azure data center traces - the first 3000 VMs (Azure-3000), the first 5000 VMs (Azure-5000), and the first 7500 VMs (Azure-7500).

There are many ways in which the Azure data center workload is different from the random workload. Firstly, the CPU requirement is generally low. In comparison to the CPU requirement, the RAM requirement for some VMs is quite high. For this workload, we assume storage to be 128 GB, similar to (Zervas et al., 2018). Thus, in most cases, storage is the most contended resource. In Figure 6, we see the characterization of the different practical workloads in terms of their CPU and RAM requirements. From Figure 6, it is seen that Azure-3000 has the lowest percentage of small VMs compared to Azure-5000 and Azure-7500. For Azure-5000, the percentage of smaller VMs is more. Azure-7500 has the greatest percentage of small VMs. Thus, the scheduling scenarios for each of these workloads are different. The network requirement for the VMs can be obtained based on Tables 1 and 2. We will see how the RISA and RISA-BF perform in the scheduling task in comparison to NULB and NALB.

Figure 7 shows the percentage of inter-rack VM assignments (out of the total number of VMs) for the three types of workloads discussed in the previous section. Here, we can see that both NULB and NALB have significant amounts of inter-rack assignments, up to $52\%$ and $48\%$ for NULB and NALB, respectively. Notably, RISA and RISA-BF have no inter-rack VM assignments for any of the workloads - showing their ability to exploit intra-rack VM allocations while leaving room for future VM requests.

For the DDC, each box only contains one type of resource, all VMs have to use the rack switch to communicate between resources regardless of where the resources reside. Thus, when the same amount of resources is used, an equal amount of intra-rack bandwidth is used to access the rack switches. For the scheduling problems in the discussion, no VMs were dropped during the scheduling process. Thus, accordingly, as seen in Figure 8, the intra-rack network utilization of all the algorithms are the same - $30.4\%$ for Azure-3000, $35.4\%$ for Azure-5000, and $42.6\%$ for Azure 7500. However, the inter-rack network utilization for all the algorithms are not the same. As explained in Section 3, RISA and RISA-BF try to minimize the amount of inter-rack VM assignments. This results in fewer inter-rack resources being used. Subsequently, resulting in lower power consumption from optical components. For the three workloads in the discussion, since there are no inter-rack VM assignments for RISA and RISA and RISA-BF, it can be seen from Figure 8 that the inter-rack network utilization is also zero.

Inter-rack switches usually have much higher port numbers in comparison to rack or box switches. This is because they connect to a large number of racks within a cluster. Thus, if an algorithm requires more inter-network bandwidth, it ends up consuming a larger amount of power from optical components, particularly from the inter-rack switches. For the power consumption calculation for optical components, we considered the transceiver power and total optical switch (box switch, intra-rack switch and inter-rack switch) power. To support the DDC architecture in Section 3, we need to have box switches with 64 ports, intra-rack switches with 256 ports and inter-rack switches with 512 ports. In Figure 9, for Azure-7500, the power consumption due to optical components is seen to be as high as $6.70$ kW and $6.72$ kW for NULB and NALB respectively. Also, it can be seen that the same power consumption for RISA and RISA-BF can be as low as $3.36$ kW for Azure-3000, whereas for NULB and NALB, the values were $5.22$ kW and $5.27$ kW respectively. This shows that RISA or RISA-BF each have $33\%$ reduction in power consumption from optical components, as compared to NULB or NALB.

Quality of service (QoS) can be an important aspect when it comes to scheduling of VMs within a DC. Since data centers sometimes run third-party workloads, QoS becomes even more of a concern, which cannot change with a change in workload. Thus, the last area of focus in comparing the three algorithms is the average CPU-RAM round-trip latency. From (Zervas et al., 2018), we assume that there is a $110$ ns CPU-RAM round-trip latency for communication within a rack, and that across racks is $330$ ns. From Figure 10, it can be seen that for Azure-3000, NULB and NALB have an average CPU-RAM round-trip latency of $226$ ns and $216$ ns respectively. For RISA or RISA-BF, it is only $110ns$. This shows that for Azure-3000, RISA or RISA-BF has lower than half of the average CPU-RAM round-trip latency as compared to NULB or NALB. Thus, RISA and RISA-BF are significantly better when QoS is of higher priority. For inter-rack center switches with a larger number of ports, the inter-rack delay may be higher, so the values in Figure 9 represent optimistic values for average CPU-RAM round-trip latency. However, since RISA and RISA-BF both out-perform NULB and NALB in terms of inter-rack VM allocations, we expect RISA and RISA-BF to have even larger improvements in CPU-RAM latency for larger systems.

For RISA or RISA-BF, when $INTRA\_RACK\_POOL$ is empty, it uses NULB for finding required compute and network resources for VM assignment. Thus, the time complexity for NULB, RISA and RISA-BF are the same. NALB performs an additional step of finding the path with the most available network bandwidth. Thus, the time complexity of NALB is higher compared to NULB, RISA, and RISA-BF. However, in practice, $INTRA\_RACK\_POOL$ is not always empty. In fact for the simulation results discussed in preceding subsections, $INTRA\_RACK\_POOL$ was never empty. Thus, in all cases, scheduling under RISA ended first. After RISA, scheduling under RISA-BF ended second, scheduling under NULB ended third, and scheduling under NALB ended last.

Table 5 lists the configuration of the system, which was used to run the simulations. Figure 11 gives a visual representation of the scheduling times of the algorithms for the synthetic workload. It can be seen that the execution time of NALB is the highest, at $865seconds$, which is followed by NULB, at $233$ seconds. RISA takes $111$ seconds and RISA-BF takes $112$ seconds. For RISA or RISA-BF this translates to greater than 2 $\times$ speedup when compared to NULB and close to 8 $\times$ speedup when compared to NALB. Figure 12 gives a visual representation of the scheduling times of the algorithms for the practical workload. Here, for Azure-7500, the execution time for NALB was $15929$ seconds and that for NULB was $10361$ seconds. For RISA and RISA-BF these values were $3679$ seconds and $4013$ seconds respectively. Thus, for RISA this translates to 2.81 $\times$ speedup when compared to the execution time of NULB. For RISA, the speedup when compared to the execution time of NALB is 4.33$\times$.