Pierre Jacquet
email: pierre.a.jacquet@inria.fr

Thomas Ledoux
email: thomas.ledoux@inria.fr

Romain Rouvoy
email: romain.rouvoy@inria.fr

SWEETSPOTVM: Oversubscribing CPU without Sacrificing VM Performance

The adoption of computing resources oversubscription in cloud environments is conventionally limited to a restricted subset of Virtual Machines (VMs) within the providers' offerings, primarily driven by performance considerations. So far, VMs schedulers mostly implement all-or-nothing oversubscription strategies, wherein all VM resources are either oversubscribed or remain unaltered. While the former strategy offers higher consolidation rates, the latter delivers better performance guarantees.

In this paper, we conducted an empirical study of the individual usage of virtual CPUs (vCPUs) in the OVHCLOUD production environment and we demonstrate that, as they are not uniformly utilized, the current holistic approach may not be appropriate. Based on these observations, we introduce a novel approach, named SWEETSPOTVM, where oversubscription ratios are applied at the granularity of individual vCPU, instead of the whole VMs. This novel paradigm unlocks a more flexible oversubscription management strategy, pinning oversubscription ratios per vCPU within VMs. We present a prototype of SWEETSPOTVM to illustrate the feasibility of accommodating multiple oversubscription levels within a single host and assigning them to individual vCPU.

We assess the viability of our approach on a physical platform, demonstrating the possibility of dividing the cost of hosting VMs by 3, while maintaining the VMs performance at the level of non-oversubscribed platforms. We, therefore, believe that SWEETSPOTVM opens new avenues to boost the consolidation of VMs on a reduced number of servers, with positive impacts on the environmental footprint of cloud computing. 2 https://www.ovhcloud.com/ VM(1) -19% VM(2) -43% VM(4) -27% VM(8) -5% VM(16) -3% VM(32) -1% VM(56) -2% CPU(1) -4% CPU(2) -20% CPU(4) -24% CPU(8) -9% CPU(16) -11% CPU(32) -7% CPU(56) -25% VM size distribution CPU distribution Physical machines

I. INTRODUCTION

Addressing the challenge of underutilized resources in cloud data centers remains a significant concern [START_REF] Barroso | The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines[END_REF], [START_REF] Delimitrou | Quasar: Resource-efficient and qosaware cluster management[END_REF], [START_REF] Lu | Imbalance in the cloud: An analysis on alibaba cluster trace[END_REF], aiming to reduce both costs and ecological footprints of these virtual platforms. The consolidation of workloads onto a smaller set of Physical Machines (PMs) improves efficiency, considering the non-linear relationship between PM power consumption and workload [START_REF] Barroso | The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines[END_REF], [START_REF] Krzywda | Power-performance tradeoffs in data center servers: Dvfs, cpu pinning, horizontal, and vertical scaling[END_REF]. This consolidation also contributes to erasing the manufacturing footprint due to unnecessary components.

Various strategies are currently employed to increase resource utilization, ranging from aggressive harvesting mechanisms [START_REF] Wang | Smartharvest: Harvesting idle cpus safely and efficiently in the cloud[END_REF], [START_REF] Fuerst | Memory-harvesting vms in cloud platforms[END_REF] to more passive approaches based on sharing [START_REF] Chen | Improving cluster resource efficiency with oversubscription[END_REF]. Oversubscription, also referred to as overallocation or overcommitment, 1 is frequently implemented by cloud providers. 1 A strategy commonly employed by cloud providers to rent more virtual resources than physically available, assuming that customers do not simultaneously utilize all the allocated resources.

However, the universal adoption of oversubscription is not privileged, as many cloud clients prioritize the performance and reliability of their allocated resources.

Within virtualization and cloud computing, workers play a pivotal role in managing virtual resources, including virtual CPUs (vCPUs) exposed to Virtual Machines (VMs) and containers. These resources are scheduled on the underlying infrastructure in a manner that accommodates the inherent heterogeneity of hosting PMs. Consequently, VMs are designed to interact with resources that appear to be uniform, with all the intricacies of hardware heterogeneity handled and managed by the host machine. In the context of oversubscription, this uniformity implies that a VM is either entirely oversubscribed or not oversubscribed at all. This dichotomous choice often leads to unused resources, as oversubscription is typically applied only to low pricing-tier VMs.

Paradoxically, beyond the VM scope, heterogeneity in resources has become the de facto industry standard. Performance heterogeneity within processor cores is now commonplace in contemporary computer systems. Simultaneous Multithreading (SMT), initially introduced in 1995 [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF], has gained extensive adoption within x86 architectures, introducing performance variability among CPU cores, based on concurrent thread utilization. Furthermore, architectural designs incorporating CPU cores with distinct frequency ranges have become increasingly prevalent. This trend is exemplified by the big.LITTLE architecture developed by ARM and, more recently, by Intel's 12th generation processors, which integrate a combination of Performance and Energy cores to achieve diverse performance objectives.

Consequently, processes are commonly scheduled in conjunction with manufacturer-specific drivers to facilitate the allocation of time slices based on variations in hardware performance. Therefore, we propose exposing vCPUs with various performance levels to VMs.

This paper introduces per-vCPU performance variations using a novel oversubscription paradigm. Instead of managing oversubscription at the granularity of a VM, we demonstrate that the vCPUs of a VM can be oversubscribed individually to different levels, enabling a more flexible management of resources at large. This innovative approach provides the capability to offer a share of resource guarantees to a VMi.e., oversubscribing to a 1:1 ratio-while concurrently sharing other resources (oversubscribing to an n:1 ratio with n > 1) across various oversubscription levels.

In the remainder of this paper, we first motivate the need for an oversubscription paradigm closer to the actual usage (cf. Section II) based on an empirical analysis of OVHCLOUD production environment, one of the largest European cloud operators [START_REF] Ovhcloud | Who are we?[END_REF]. We, then, detail how oversubscription can be implemented at the vCPU granularity (cf. Section III). We evaluate our prototype in Section IV using realistic Infrastructureas-a-Service (IAAS) workloads and report on our ability to selectively guarantee computing resources. Finally, we discuss related work (cf. Section V) before concluding in Section VI on this work and its perspectives.

II. MOTIVATION

In this section, we motivate the need for another oversubscription paradigm that better fits to individual vCPU usage.

A. Not all vCPUs are equally used

The cloud is characterized by its heterogeneous workload, covering VMs hosting storage-oriented services, batch processes, or interactive applications. IAAS customers have the flexibility to configure the level of computing power, typically indicated by a number of vCPUs to provision, based on their workload type and anticipated demand (e.g., peak requests per second on a website).

Cloud providers commonly analyze the utilization of initial resource allocations through VM CPU usage, a metric often included in the cloud datasets shared with the research community [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF], [START_REF] Alibaba | The alibaba clusterdata201708 trace data[END_REF], [START_REF] Google | Borg cluster traces[END_REF]. However, global VM usage does not allow for the differentiation of various workload situations. For instance, a VM configured with 4 vCPUs and utilizing 25% of its CPU time may concentrate its workload on a unique vCPU in a CPU-intensive single-threaded context, or evenly distribute it across all vCPUs in a fully multi-threaded workload.

To the best of our knowledge, the individual usage of VM vCPUs has not been previously studied. We, therefore, conducted such an analysis using exploitation traces from an production-scale IAAS environment operated by OVHCLOUD, a major cloud provider. 2 This analysis results from the monitoring of an OPENSTACK computing platform over a 1-week window, where the CPU time for each vCPU associated with each VM was recorded at 5-minute intervals. We consider a premium offer that delivers dedicated resources-i.e., no oversubscription is implemented (1:1)-thereby precluding the examination of contention situations.

Figure 1 first reports on the distribution of provisioned VM configurations on the left-hand side. The right-hand side of the Sankey diagram highlights how these VM configurations map to the CPU that are effectively provisioned by the PMs upon deployment. While the smallest VM configurations seem to be prevalent in IAAS platforms (62 % of the VM configurations include at most 2 vCPUs), as previously acknowledged Fig. 1. Mapping the distributions of VM sizes to the physical CPUs provisioned by the OVHCLOUD infrastructure by [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF], the share of provisioned CPU highlights that the largest VM configurations are the ones which consume most of the computing resources exposed by the PMs, with 76 % of the CPUs being provisioned by VMs requesting at least 4 vCPUs.

Beyond this first observation, we further dive into the effective usage of individual vCPUs by the different VM configurations. To do so, we derive an utilization metric, and we order the vCPUs from the most utilized (designated as vCPU0) to the least utilized (designated as vCPU(n -1), where n is the VM size). It is essential to note that during the 5-minute aggregation period, the guest scheduler of each VM has the freedom to relocate processes from one vCPU to another. This allocation may be based, for instance, on the Completely Fair Scheduler (CFS) queue calibration mechanism [START_REF] Wong | Towards achieving fairness in the linux scheduler[END_REF]. The substantial differences observed in vCPU time after a 5-minute interval underscore the significance of these variations, indicating that the workload could not be uniformly distributed across all VM resources during this time frame.

However, optimal performances on a given platform are typically obtained for a CPU charge below 100% due, among others, to SMT and cache contention. To account for it, a vCPU is labeled as active even if it does not consume 100% of the associated window CPU time. To perform a sensibility analysis of this threshold, we examined 3 values to label a vCPU as active: 1%, 10%, and 30%.

Our results are plotted as Cumulative Distributed Functions (CDFs) in Figure 2. For each graph, the Y-axis represents the share of VMs, while the X-axis denotes the proportion of time during which the vCPU can be deemed active, based on the considered threshold (indicated in the caption). For instance, when focusing on the last CDF (lower right) for VMs with 16 vCPUs and an activity threshold of 30%, the comparison is as follows: for 80% of the VMs (Y-axis), vCPU0 (indicated by the red line) is considered as active 100% of the time (Xaxis) with the intersection at point A. In contrast, the least used vCPU, namely vCPU15, is considered as active less than 50% of the time (intersection at point B).

We first observe that the vCPU0 line can be distinguished in most of the graphs, having an activity threshold higher than 1%, indicating that during a significant proportion of the time, the workload is mono-threaded. This highlights that not all the IAAS workloads are multi-threaded, and not every multithreaded workload leverages all the vCPUs provisioned by a VM.

Then, one can observe that larger VMs tend to exhibit a nonuniform usage of their vCPUs. Except vCPU0, 2 vCPUs with close indices (such as vCPU1 and vCPU2) typically report a low usage shift. As this shift is cumulative, it becomes all the more pronounced between the least used and the most used vCPUs, especially in larger VM sizes.

Single-core VMs tend to be less used, indicating that they may be preferred by clients for non-CPU-oriented workloads. However, less-used cores in larger VMs are close to the usage observed in single-core VMs. The count of unused resources is amplified in the case of bigger VMs as they individually have more cores matching this low-usage pattern. This leads us to conclude that the larger the VM, the more resources are wasted by the cloud infrastructure.

We can, therefore, conclude that i) the largest VMs are provisioning most of the computing resources, and ii) these provisioned resources fail to be fairly consumed, hence leading to wasted resources.

While one could expect the cloud customers to size their VM appropriately, there are many reasons that can explain the provisioning of large VMs with a non-uniform resource usage pattern, among which the lack of predictability of resource usage or the over-provisioning of resources to address potential usage peaks. Cloud providers, therefore, have to cope with this issue and find an alternative to reduce the non-negligible wastes of computing resources imposed by the number of provisioned vCPU that are not effectively used.

In the following sections, SWEETSPOTVM introduces the principle of vertical oversubscription as a solution to mitigate performance requirements and resource utilization, aiming to reconcile both dimensions.

B. Introducing vertical oversubscription

The oversubscription of cloud resources remains a nontrivial exercise as a compromise has to be made between leveraging under-utilized capacity and performance, by avoiding Service-Level Agreement (SLA) violations. This is challenging as the specific cloud context implies hosting heterogeneous types of workloads, with almost no direct information on individual workloads, given that cloud providers are operating VMs as black-boxes.

Each PM of a given cloud context is singular. Tuning an oversubscription ratio at the cluster level (e.g., the factor applied to all the PMs), while trying to avoid SLA violations on edge situations, leads to configure pessimistic ratios, hence missing resource optimization opportunities.

The mapping of virtual resources of a VM to the physical resources of a PM can be implemented in different ways. Specifically, the oversubscription scope plays a critical role when accounting for exceptional situations-i.e., those likely to provoke SLA violations. Transitioning from a cluster scope to a server scope, which involves defining a ratio of exposed virtual resources per server, enables the consideration of both hardware heterogeneity [START_REF] Wang | A scheduling algorithm based on resource overcommitment in virtualization environments[END_REF] and workload heterogeneity [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF], [START_REF] Bashir | Take it to the limit: Peak prediction-driven resource over-commitment in datacenters[END_REF]. We believe that this shift in scopes has the potential to further yield more optimistic ratios. In particular, to better reflect individual usages, the oversubscription computation scope needs to be extended beyond the per-server limit. In opposition to the current oversubscription paradigm, which treats all resources equally in a horizontal manner, as depicted in Figure 3, we advocate for an orthogonal approach, hence qualified as vertical oversubscription. In this paradigm, the consumers of the PM resources are considered to be the vCPUs, in contrast to the VMs, thereby lowering the scope granularity.

Similarly to hardware architectures with cores operating at different maximum clock frequencies (e.g., big.LITTLE processor architectures), this leverages oversubscription ratios to introduce different levels of performance within a VM. The vertical oversubscription paradigm allows, for example, a cloud provider to guarantee performances on a restricted set of cores (associated with low or even no oversubscription), while also mutualizing resources on others (associated with higher oversubscription ratios).

III. IMPLEMENTATION DETAILS

Conventional horizontal oversubscription paradigm exhibits resource allocation at a host-based granularity, wherein the pool of resources associated with a particular PM is uniformly distributed among all vCPUs relying on the Linux scheduler for sharing time slices.

In contrast, our vertical oversubscription paradigm assumes a non-uniform distribution of physical resources among provisioned vCPUs. Specifically, some premium vCPUs may be allocated to dedicated physical resources, while others may be subject to oversubscription. In this section, we explore the coexistence of various oversubscription ratios on a single PM.

A. Local scheduler

A cloud scheduling architecture can be summarized as two main software components [START_REF] Wuhib | Dynamic resource allocation with management objectives-implementation for an openstack cloud[END_REF], [START_REF] Jennings | Resource management in clouds: Survey and research challenges[END_REF].

The first one is a global scheduler, also known as the control plane, which handles incoming VM deployment requests and selects the most suitable PM for deployment. It typically achieves this by communicating with an agent located on each PM, referred to as the local scheduler, to gather information about the PMs's current state.

Once a PM is selected as the target, the VM deployment request is forwarded to the local scheduler. The local scheduler generally assumes responsibility for provisioning tasks, such as creating a disk image, invoking the hypervisor to initiate the VM, and, in some cases, determining how resources are allocated among the VMs, possibly utilizing features like cgroups for resource management.

In SWEETSPOTVM, the capabilities of the local scheduler are expanded to include the management of multiple oversubscription ratios. The PM resources are logically separated through distinct pools of vCPUs. Each pool is associated with a given oversubscription ratios and is size can be adjusted dynamically, depending on hosted VMs.

A pool comprising n cores can support a maximum of n vCPUs in the absence of oversubscription. At a 2:1 oversubscription ratio, 2n vCPUs can be accommodated, and this applies to any oversubscription ratio. The logical segregation mechanism is further discussed in Section III-B.

Our local scheduler interfaces with the hypervisor using the libvirt library and has been tested with QEMU/KVM as the hypervisor of choice due to its support for dynamic CPU pinning changes.

B. Segregate physical cores

The non-uniform distribution of resources between vCPUs necessitates the utilization of distinct resource pools, each characterized by a specific oversubscription ratio. This allocation is achieved by implementing a shared CPU affinity policy, wherein vCPUs are affixed to a common set of cores on the PM.

We identified and addressed two main challenges. Firstly, the performance and isolation of PM core selection are intricately linked with the PM topology, as established in existing literature [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF]. However, the applicability of our heuristics across diverse architectures is imperative, given the heterogeneous configurations prevalent in cloud data centers [START_REF] Wang | A scheduling algorithm based on resource overcommitment in virtualization environments[END_REF] Secondly, the size of the vCPU pools needs to be dynamically adjusted to cope with unforeseen IAAS workload (covering VMs of various sizes).

1) Generic core selection: Contemporary PMs exhibit intricate processor topologies, potentially featuring heterogeneous distribution of cache levels or multiple sockets, making the segregation process not trivial.

The process of selecting an appropriate core for a given task usually relies on both the Linux scheduler and manufacturers' drivers responsible for managing features, such as C-States and P-States. Manufacturers' drivers may take decisions, such as loading a specific core to harness Turbo-boost capabilities or distributing a workload to optimize cache resource utilization.

These decisions are contingent upon the hardware configuration and the chosen scaling governor.

Directly pinning processes to specific cores would circumvent the involvement of these components, posing a significant threat to the universality of our strategy. In practical implementation, instead of selecting individual cores, we opt for the selection of a range of cores, even in the case of premium vCPUs.

The selection of cores is undertaken with the objective of closely aligning with the characteristics of the processor topology, hence leveraging the optimizations of manufacturer driver capabilities. When expanding a pool of physical resources to accommodate a newly provisioned vCPU, the selection of cores is predicated by a distance metric.

The computation of the distance between two cores depends on their degree of shared cache, where cores with a lower level of shared cache, such as in a SMT topology, are deemed closer than cores with no shared cache. Note that configurations where the last level of cache is not be universally shared are common, such as in a multi-socket architectures or with AMD EPYC processors.

Algorithm 1 Distance (∆) computation between 2 cores

Input: core 0 , core 1 Output: ∆ 1: ∆ ←0 2: for <cachelevels> do 3:

if LEVEL(core 0 ) == LEVEL(core 1 ) then 4:

return ∆

5:

end if

6:

∆ ← ∆ + 10 7: end for 8: return ∆ + NUMA-DISTANCE(core 0 , core 1 )

To account for it, we introduce a core distance metric extending the Non-Uniform Memory Access (NUMA) distance [START_REF]Numa binding description[END_REF]. This extended metric incorporates an assessment of the shared cache levels to provide a more complete evaluation of core proximity. Linux system exposes for each core and cache level an ID to identify the cache zone. We retrieve this data and compute distances between each core, as described in Algorithm 1. While the incremental value is arbitrary, we chose it to be in the same order of magnitude as the current NUMA distance notion.

The selection of a core closer to the existing pool ensures that the newly added physical resources share cache levels, resembling the characteristics associated with a socket of the same architecture but with a reduced core count. Consequently, in an SMT topology, cores within the same physical unit are assigned to a common pool.

From a process scheduling perspective, Linux engages sibling cores only when all physical cores are in use, to mitigate performance degradation. In comparison to a scenario where each non-oversubscribed vCPU is assigned to a single personal physical core, we rather considered them as a group and pin them to a range of physical CPUs. If the number of vCPUs matched the number of physical CPUs associated, the non-oversubscribed status is sustained, and the approach let the CFS scheduler manage the distribution of work. This approach maintains the drivers and scheduler behavior, thereby averting performance deterioration due to SMT (as vCPUs do not consistently exceed 50%) while judiciously employing it during peak demands.

2) Pool resizing: A VM with n vCPUs may have a maximum of n different oversubscriptions levels (one for each vCPU). The allocation of a VM to each pool of resources is, therefore, dependent on its size. Some VM may have a vCPU allocated to a given pool while others do not or, some VM may have more vCPUs associated with a given pool than others.

The dynamic nature of VMs encourages a dynamic pool size. Rather than defining the size of each pool statically, the allocation is changed upon each deployments. This flexibility accommodates the uncertainty associated with the number of VM creation requests, enabling our system to efficiently allocate resources in response to varying workloads.

A VM deployment is implemented as the assignment of its vCPUs to the associated vCPU pools. If a pool is not sufficient to provision a new vCPU, this pool can automatically grow by selecting the closest unallocated core from its current configuration. In practice, this implies changing the pinning of VMs having at least one vCPU in the considered pool to accommodate the new range. While frequent changes in core pinning can potentially introduce performance overhead due to increased context switches, it is important to note that, in our specific context, such changes are infrequent occurrences. They only occur when a VM is being deployed or decommissioned. These VM deployment and decommissioning events do not happen at a high frequency within the time scale of CPU operations.

If a pool size extension fails due to a lack of available resources, the VM deployment is rejected by the local scheduler. Furthermore, VM departures from the system do change the allocation to accommodate future deployments.

C. Pool heterogeneity requirements

In a n:1 oversubscription scenario, a cloud provider guarantees that no more than n vCPUs can contend for a single physical core. However, oversubscription relies on workload heterogeneity and the assumption that unused resources by some VMs can be utilized by others.

Consequently, a VM should not be oversubscribed with itself, as this mislead the guest into expecting a certain level of CPU availability that is impossible to receive in practice. The introduction of oversubscription with 2 VMs can also pose a significant risk of performance degradation. This risk diminishes when more VMs are being provisioned, as the probability of all VMs simultaneously reaching their peak usage diminishes.

In an horizontal setting, while each PM may have an oversubscription objective, its resources are only effectively oversubscribed when the number of virtual resources provisioned exceeds its configuration. This guarantees a certain heterogeneity in the workload. In our vertical context, oversubscription may occur earlier, as we limit the resources available for use by vCPUs. For example, a subset of physical resources may be oversubscribed before all cores are allocated.

To mitigate the risks of contention associated with oversubscribed contexts, we increase workload heterogeneity when possible. In practice, it is possible to allocate different oversubscription levels of VMs to the same set of resources provided that they adhere to the conditions imposed by the lowest oversubscription level within the VM set. In simpler terms, a vCPU with a 2:1 oversubscription level may coexist with a vCPU having a 3:1 oversubscription level, but only if the set of physical resources still complies with the 2:1 ratio (as the "no more than 2 vCPUs per physical core" condition satisfies the "no more than 3 vCPUs per physical core" condition).

While this approach increases the allocated resources, as the 3:1 overcommitted vCPU is "upgraded", it may be strategically employed to enhance workload heterogeneity temporarily, if there are some unallocated resources to leverage. Alternatively, remediation mechanisms, like those involving cgroups are feasible, but they may be considered at odds with the oversubscription principle, which aims to distribute the pool of resources equally among all consumers.

Hence, our strategy relies on the pooling of oversubscribed vCPUs when feasible, effectively leveraging all resources that remain unallocated by the current hosted VMs. Upon deployments, we also prevent VMs from being oversubscribed with themselves by verifying than the pool size is greater than the requested virtual resources.

D. Oversubscription templates

In a vertical oversubscription scenario, the vCPUs of a given VM may be oversubscribed to different ratios. This is achieved using what we term an oversubscription template.

A template is a configuration specifying an oversubscription ratio for each vCPU index (or range of vCPUs). While any vCPU can be oversubscribed to any positive amount, we believe that using progressive oversubscription ratios is a good practice. The VM should be aware of the performance of its individual cores to leverage the most of our approach. A general rule stating "the lower the vCPU index is, the better the performance" emphasizes that.

Oversubscription templates are configurable and may be changed by cloud providers to match the specificities of their workloads.

IV. EMPIRICAL EVALUATION

In this section, we discuss how our vertical oversubscription paradigm was evaluated.

A. On core priority

While a VM workload may not use more than the equivalent of one core at a given time, its workload may be spread through all its vCPUs due to the CFS behavior. However, in a vertically oversubscribed scenario, performance obtained by a VM is improved if its workloads foster its least-oversubscribed cores.

This can be done in different manners, such as pinning inside the VM the workload of interest. More generic approaches imply to develop a specific Linux scheduler and/or a driver.

In our evaluation, we used a third approach based on a root daemon running on each VM. The daemon, composed of around 150 Python lines of code, computes the CPU usage each 200 ms. The minimal number of cores required to run this load is deducted and applied by deactivating unnecessary VMs cores. Deactivation is executed in decreasing core index order, deactivating the farthest index cores as they are the least powerful ones in our template. This consolidation strategy aims to concentrate the workload on the most powerful cores, with vCPU0 exhibiting the highest performance. If more than 80% of the activated cores are used, a new one is permitted, allowing to handle an increasing intensity in the workload.

This approach implies a certain latency before activating all cores, however, we found it to be acceptable for the size of VMs considered. Activating all cores in a VM composed of 8 vCPUs is performed in a maximum of 7 × 0.2 = 1.4 seconds (assuming we start in the worst case from having only vCPU0 activated).

B. On workload generation

Our proposed solution was tested on a physical platform to assess VM performances.

The input is generated from customer traces, encompassing actions, such as VM creation, VM usage, and VM deletion. This compilation of customer activities is collectively referred to as the "workload".

Ensuring the inclusion of realistic workloads was paramount in our context, given that oversubscription relies on a heterogeneous usage of resources by customers. To achieve this, we chose to utilize CLOUDFACTORY [START_REF] Jacquet | Cloudfactory: An open toolkit to generate production-like workloads for cloud infrastructures[END_REF] for workload generation. This decision was motivated by the tool's capability to generate workloads that match statistics in terms of VM usage patterns. The workload was composed of an increasing number of VMs, each having 8 vCPU, overall matching the CPU usage observed in Azure context [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF].

The considered VMs hosted two distinct types of applications. Firstly, there was a micro-services architecture, known as Social Network, derived from the DEATHSTARBENCH [START_REF] Gan | An Open-Source Benchmark Suite for Microservices and Their Hardware-Software Implications for Cloud & Edge Systems[END_REF]. The response times of these micro-services were continuously monitored and utilized as a proxy for the individual performance of the respective VMs. While being dynamic through time, the applied input ranged between 10 to 1,000 requests per second. Secondly, the StressNG load test was applied to a second set of VMs. This load test facilitated the precise load on CPU resources for each VM, contributing to an overall realistic context on the given host. The load of each VM was also dynamic and could change between 0% and 100% of resources used every 90 seconds.

C. Experimental IAAS platform

For our example, we used the PM described in Table I as a worker node. Of the 256 cores, 20 were kept for the

D. Experimental results

We applied the same workload in different contexts. Initially, as a baseline, we executed the workload without considering oversubscription, thereby limiting the virtual resources to the amount proposed by the platform. This configuration is used to set our ground truth as being the optimal performances that can be obtained from our experimental testbed.

The evaluation and comparison of the considered oversubscription techniques was conducted in both horizontal (single ratio) and vertical (multiple ratios) approaches. Specifically, we measured performances under platforms with average oversubscription ratios of 2:1, 3:1, and 4:1. In the horizontal approach, the targeted ratio was uniformly applied to all the provisioned vCPUs. In the vertical approach, the oversubscription template was chosen to have, on average, the same ratio as the one targeted by the horizontal configuration. For example, with a 3.0 oversubscription ratio, 1 vCPU was dedicated for each VM (referred to as vCPU0), one was oversubscribed to a 1.5:1 ratio (vCPU1), and all others were oversubscribed to a 6:1 ratio (vCPUn, for n within 2 to 7). For a workload composed of VMs with 8 vCPUs, this led to an average oversubscription ratio of r = vCP U CP U = 8

(1/1)+(1/1.5)+(6/6) = 3.0. Other templates used by SWEETSPOTVM are described in Table II. While these choices are arbitrary and can be customized by the cloud provider, we selected templates that dedicate part of the resources-i.e., no oversubscription on vCPU0-while oversubscribing others more aggressively to match the ratio. This type of template allows us to illustrate the heterogeneous usage being made of vCPUs. The performance of each context, evaluated through the 95 th response time of each exposed service, is visualized in Figure 4. Unsurprisingly, the baseline without any oversubscription exposes a good response time, as no vCPU is competing for resources nor SMT is required (as the overall CPU usage remains below 50%).

Under a 2:1 oversubscription template, where the number of hosted VMs is doubled, both vertical and horizontal approaches perform similarly. There is no significant performance degradation (please note the logarithmic scale) with the traditional (horizontal) approach, indicating that pinning vCPUs differently does not notably improve performance.

Under a 3:1 oversubscription template, host resources are still not fully utilized. However, performance decreases significantly with the traditional approach, while our vertical oversubscription template keeps maintaining VM performances closer to their optimal values, succeeding hosting more VMsi.e., 3× more than the baseline.

The performance gain is even more significant with the 4:1 oversubscription template. In this situation, the horizontal approach leads to an overloaded CPU, and fewer time slices being attributed to each vCPU (note that the Y-axis scale had to be adjusted accordingly). Using a vertical approach, the contention is limited to only a subset of the vCPUs of the VM, and the vCPU0 keeps exhibiting good performances, compared to the horizontal oversubscription. This demonstrates that vertical oversubscription can be adopted to mitigate the effects of an overloaded situation.

As such, oversubscription can be used to introduce different levels of performance on different cores. When VMs uses their most powerful cores (the less shared ones) in priority, performances can be close to the optimal.

The VM count is emphasized in Figure 5. Our strategy does host the same number of vCPUs and, therefore, the same number of VMs. When the average oversubscription achieved is not an integer, small differences may appear, which may be mitigated by changing the oversubscription templates. In this example, our average oversubscription was slightly above the 2:1 target (leading to one additional deployment), while being slightly below the 4:1 target (leading to 3 fewer deployments). Notably, one should note that the quantity of memory (VRAM)-and its potential oversubscription-is not affected, compared to a horizontal oversubscription mechanism, as the number of VMs hosted is similar for the same targeted oversubscription ratio. The performance degradation is expressed here in the form of the multiple of the 95 th response time of the baseline. In the 2:1 oversubscription scenario, the degradation is reduced by 10% (from 1.8 times the baseline to 1.6), by half in the 3:1 oversubscription scenario (from 2.9 times the baseline to 1.3), and by a factor of 50 in the 4:1 situation (from 107 times the baseline to 2.1 times). While variability may be observed due to other resources (such as the network), the performance degradation is clearly mitigated by SWEETSPOTVM compared to state-ofthe-art strategies enforcing horizontal oversubscription.

By dedicating CPUs to the VMs and oversubscribing others more aggressively, our scheduler succeeds in preserving performances by considering the heterogeneous usage made by VMs of their vCPUs. Specifically, with the last oversubscription ratio having no contention, r = 3.0, our approach closely aligns with the performance of the non-oversubscribed scenario, while allowing the deployment of 3× more VMs in that case.

The allocation size of the different oversubscription levels targeting an average oversubscription of 2:1 is depicted in Figure 6. The premium subset, dedicated to all vCPU0, provisions 59 physical cores under our workload. Its usage remains low compared to its allocation size, avoiding any concurrency issues (at most 40 cores, 68% of the provisioned resources). The second subset, dedicated to vCPU1, reports on the same number of vCPUs attributed. However, as vCPU0 concentrates most of the workload, the vCPU1 subset exhibits a lower core usage, with only 31 physical cores being effectively used (21% less than the 40 cores). The last subset has a much larger number of hosted vCPUs, as each VM allocates 6 vCPUs to this oversubscription ratio. Its 136 attributed cores were used, with a peak of up to 51% of the provisioned resources.

The performance obtained from the VM perspective depends on the contention observed in the pool of host resources considered. In this example, while the 2:1 is the most oversubscribed one, no contention is observed (as the size of the allocation is far greater than its usage), leading to good performance even on the least powerful VM vCPUs.

E. On the provisioning of small VMs

Our paper focused on the use case of relatively large VMs, due to both their proportion in the count of provisioned vC-PUs and their tendencies to have non-uniform usage patterns between their individual vCPUs, as exemplified in Section II. Nonetheless, nothing prevents SWEETSPOTVM from hosting smaller VM configurations in conjunctions with larger VMs as it uses to be case in production-scale IAAS platforms. In particular, SWEETSPOTVM can accommodate smaller VMs by allocating their VMs to non-oversubscribed pools, hence preserving their quality of service, based on the observations we drawn from Figure 2.

V. RELATED WORK

A. Resource oversubscription

Most hypervisors enable oversubscription by allowing the sum of all allocated virtual resources to exceed the PM capabilities [START_REF] Citrix | Overcommiting pcpus on individual xenserver vms[END_REF], [START_REF] Vmware | Cpu virtualization basics[END_REF], [START_REF] Proxmox | Proxmox ve administration guide[END_REF]. To avoid SLA violations, oversubscription is usually limited at a certain level, quantified as a ratio between the number of virtual resources provided and the available physical resources.

To the best of our knowledge, this ratio is only applied horizontally (albeit homogeneously through all vCPUs) by stateof-the-art cluster managers. For instance, OPENSTACK [START_REF] Openstack | overcommiting cpu and ram[END_REF] and BORG [START_REF] Verma | Large-scale cluster management at google with borg[END_REF] restrict the oversubscription of resources by utilizing a single static value for the entire cluster PMs.

The horizontal oversubscription was also proposed to be defined per PM. It may be static, by taking into account individual PM performance [START_REF] Wang | A scheduling algorithm based on resource overcommitment in virtualization environments[END_REF]. Alternatively, it can be dynamic, relying on predicted peak usage [START_REF] Bashir | Take it to the limit: Peak prediction-driven resource over-commitment in datacenters[END_REF], as new deployments must be performed on resources seen as available in the long run. Peak prediction may be computed using VM percentile [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF] or standard deviation [START_REF] Bashir | Take it to the limit: Peak prediction-driven resource over-commitment in datacenters[END_REF]. However, none of these approaches dive into the actual usage workloads within each VM, which may not utilize all their vCPUs homogeneously. Each PM maintains a single oversubscription level, determined by its configuration or the cluster-scale configuration.

In this paper, we proposed a vertical oversubscription paradigm, where each vCPU may have an individual oversubscription level. This approach allows cloud providers to better fit consumer requirements (by considering the vCPUs rather than the VM), achieving more optimistic oversubscription ratios while guaranteeing a minimum amount of available resources.

B. Performance heterogeneity

Performance heterogeneity for VMs has been previously investigated to improve energy proportionality [START_REF] Costa | Heterogeneity: The key to achieve power-proportional computing[END_REF], [START_REF] Villebonnet | big, medium, little": Reaching energy proportionality with heterogeneous computing scheduler[END_REF], [START_REF] Villebonnet | Dynamically building energy proportional data centers with heterogeneous computing resources[END_REF], [START_REF] Rocha | Heats: Heterogeneity-and energy-aware task-based scheduling[END_REF]. This is achieved by migrating VMs between PMs with different architectures depending on the VM workload. This approach is also horizontal, as the performance is adapted for all the provisioned vCPUs. In our proposal, performance heterogeneity does not arise from hardware differences, but rather from the applied oversubscription ratio, enabling a more flexible management and a better resource packing. Yet, SWEETSPOTVM offers a complementary approach to cope with hardware heterogeneity and to contribute to the implementation of energy proportionality in cloud infrastructure while minimizing the number of PMs required to host a set of VMs.

VI. CONCLUSION

In conclusion, this paper has introduced SWEETSPOTVM, a novel oversubscription paradigm that addresses per-vCPU performance variations, departing from the conventional approach of oversubscribing resources at the VM granularity. By demonstrating the feasibility of individually oversubscribing vCPU to different extents, we have introduced a more flexible resource management strategy for IAAS platforms supporting the cloud industry. In particular, this innovative approach allows cloud providers to propose resource guarantees to a VM on a 1:1 ratio, while concurrently reallocating other resources across potentially multiple oversubscription levels (n:1 ratio with n > 1).

Our contribution is implemented as a functional software prototype, leveraging cache level distance between cores to efficiently segregate multiple oversubscription levels. Our evaluation demonstrates that the performances achieved by a nonoversubscribed environment can be replicated in an oversubscribed context, allowing cloud providers to consider the generalization of oversubscription and therefore, drastically reducing the number of servers required to host their customer services and the associated workloads.

We foresee several perspectives for this work, notably on the applied oversubscription templates. While these templates are defined statically in this paper, we believe that they could also benefit from more dynamic tuning approaches, including techniques where the targeted template configuration is driven by performance objectives rather than a fixed ratio. Examining the impact of diverse oversubscription templates based on VM size or distinct premium tiers is also left as a prospect for future work.

SOFTWARE ARTEFACTS

For the sake of reproducibility of the empirical results we shared in this paper, our software prototype is made publicly available. 3 In particular, we documented an offline mode to reproduce all the reported experiments. Furthermore, the daemon used in the experiments to prioritize the cores with lower indexes inside the VMs is also available. 4

Fig. 2 .

 2 Fig. 2. CDF of individual vCPU utilization ratios of various VMs profiles hosted by OVHCLOUD.

Fig. 3 .

 3 Fig. 3. Transitioning from horizontal CPU oversubscription to vertical oversubscription as implemented by SWEETSPOTVM

Fig. 4 .

 4 Fig. 4. DEATHSTARBENCH social network response time on different oversubscription scenarios

Fig. 5 .

 5 Fig. 5. Performance degradation in response time of the social network app of DEATHSTARBENCH (as multiple of the baseline)

Fig. 6 .

 6 Fig. 6. Evolution of resources allocation and usage per oversubscription level for a SWEETSPOTVM template targeting 2:1

TABLE I HARDWARE

 I SETTINGS OF OUR IAAS WORKER NODE

	Processor	AMD EPYC 7662 64-cores ×2
	Total threads 2 × 64 cores × 2 hyperthreads = 256
	Memory	1 TB
	OS	Linux Redhat 8.6
	Hypervisor	QEMU & KVM 7.1

ACKNOWLEDGMENTS

This work is supported by the "FrugalCloud" Inria and OVHCLOUD partnership. Additionally, this work also received partial support from the French government through the Agence Nationale de la Recherche (ANR) under the France 2030 program, including partial funding from the CARECLOUD (ANR-23-PECL-0003), DIS-TILLER (ANR-21-CE25-0022), and SeMaFoR (ANR-20-CE25-0017) grants.


Alexandre Dolgui

Maksim Pashkevich

Anatoly Pashkevich

Frédéric Grimaud
email: grimaud@emse.fr

Forecasting risk analysis for supply chains with intermittent demand

Keywords: inventory control, demand modelling, forecasting risk, robust prediction, error correction

This paper focuses on the forecasting risk analysis in supply chains with intermittent demand, which is typical for the inventory management of the 'slow-moving items', such as service parts or high-priced capital goods. The adopted demand model is based on the Generalised Beta-Binomial Distribution (GBBD), which is capable of incorporating the additive distortions in the demand historical records as parameters. For this setting, there are proposed explicit expressions for forecasting risk and the prediction function, which minimises the error impact on the risk. The efficiency of the proposed approach is confirmed by computer simulation and is illustrated by an application example for forecasting of the intermittent demand values for car spare parts.

Introduction

Recently, performance measuring in manufacturing and logistics has been highlighted by a number of researchers. Owing to growth of enterprise collaboration and new challenges in managing supply chains, risk evaluation has become a very important issue. This paper focuses on minimising the forecasting risk for inventory management in supply chains with intermittent demand in the case of reporting errors in the past demand records.

For large-scale supply chains, accurate demand forecasting is motivated by strong financial incentives, since there is a high need to balance the customer service levels against investments over a large assortment of Stock-Keeping Units (SKU) [START_REF] Harris | Optimized inventory management[END_REF][START_REF] Hopp | Factory Physics: Foundations of Manufacturing Management[END_REF][START_REF] Silver | Inventory Management and Production Planning and Scheduling[END_REF]. As follows from related research [START_REF] Snyder | Forecasting sales of slow and fast moving inventories[END_REF], a large proportion of SKUs is usually made up of 'slow-moving items' with irregular (intermittent) demand patterns, that is, random sequences with a large proportion of zeros and great variability among the remaining non-zero integer values [START_REF] Willemain | A new approach to forecasting intermittent demand for service parts inventories[END_REF]. A typical case study of NSK Corporation (Ann Arbor, MI, a precision parts manufacturer for the automotive industry) reported by [START_REF] Smart | Accurate intermittent demand forecasting for inventory planning: new technologies and dramatic results[END_REF] shows that two-thirds of the 7000 SKUs demonstrate highly intermittent demand behaviour, with half of the zeros in the history data. Similar demand patterns are common for all the service parts businesses in the aerospace, automotive and high-tech electronics industries. The intermittent demands are also usual for high-priced capital goods, such as heavy machinery, where the inventory replenishment lead times can be up to several months, and the costs may reach several hundred thousand dollars.

In contrast to the standard marginal stock level setting, the inventory management of the slow-moving items requires a probability distribution of the SKU demand. It is used to generate the demand forecasts, which are key inputs to the inventory control models allowing to correct time and size of replenishment orders (reorder points and order quantities). Besides, the demand distribution is particularly important for estimating the customer service level (e.g. a 95% or 99% likelihood of not stocking out over a lead time). In such situation, the conventional statistical forecasting methods (exponential smoothing and moving averages) are limited to forecasting of the average demand per period only. They are not able to produce credible results for the complete set of all possible demand values, since they implicitly assumed the normal, bell-shaped distribution, which ignores both the integer nature of the historical data and special role of zeros. And with the intermittent data, the distribution shape can be essentially non-symmetric and even non-unimodal, with several maximums. So often, the conventional methods may produce misleading inputs to inventory control models, with rather costly consequences [START_REF] Grange | Challenges in modeling demand for inventory optimization of slow-moving items[END_REF][START_REF] Hopp | Easily implementable inventory control policies[END_REF]. For this reason,it is important to apply an adequate demand probability distribution that ensure accurate reorder points forecast.

The first heuristic technique for the intermittent demand forecasting was developed by [START_REF] Croston | Forecasting and stock control for intermittent demands[END_REF] who applied separate exponential smoothing to both the non-zero demand sizes and inter-arrival times between successive demands. Later, the problem was addressed by a number of authors [START_REF] Willemain | Forecasting intermittent demand in manufacturing: a comparative evaluation of Croston's method[END_REF][START_REF] Johnston | Forecasting for items with intermittent demand[END_REF][START_REF] Syntetos | On the bias of intermittent demand estimates[END_REF] who concentrated on improving the forecast accuracy and proposed several modifications of the Croston's method, including EWMA-smoothing and log-transformation of the data (both the demand values and inter-arrival times) in order to avoid the positive-space constraint. However, the corresponding model variables were still deterministic and defined in a continuous space. Consequently, all of these methods do not produce forecast distributions and associated prediction intervals (Hyndman and Shenstone 2003).

The first stochastic demand models were based on the Poisson or NBD (negative-binomial) distributions, and they originated from research on stochastic inter-purchase times and proved to be very accurate in the fitting of the aggregated data describing frequently purchased goods [START_REF] Agrawal | Estimating negative binomial demand for retail inventory management with unobservable lost sales[END_REF][START_REF] Dunn | An investigation of the assumptions of the NBD model as applied to purchasing at individual stores[END_REF][START_REF] Grange | Challenges in modeling demand for inventory optimization of slow-moving items[END_REF][START_REF] Gupta | Stochastic models of interpurchase time with time dependent covariates[END_REF][START_REF] Wagner | Stochastic models of consumer behaviour[END_REF]. However, their basic assumption on exponential (or gamma-exponential) distribution of the inter-arrival times does not take into account the multimodality, which becomes a vital issue for personalisation of the marketing decisions. To overcome this problem, [START_REF] Telang | A mixture model for internet search engine visits[END_REF] proposed recently a hierarchical probabilistic model of user's repeat visits that incorporates Weibull, Laplace and double-exponential mixed distribution to account for users' schedule. This model was successfully applied to forecasting of visits to massively popular internet websites, but it seems to be hardly applied to the intermittent demand modelling, which possesses the above-mentioned specificities. In this paper, the multimodality is resolved within the Bayesian framework [START_REF] Azoury | A comparison of the optimal ordering levels of Bayesian and non-Bayesian inventory models[END_REF], using the Generalised Beta-Binomial Demand Distribution (GBBD) developed in our previous paper [START_REF] Dolgui | Modeling demand for inventory management of slow-moving items in case of reporting errors[END_REF].

However, even when the selected stochastic model of the demand is adequate, it still can be misleading in cases of reporting errors in the demand records [START_REF] Jacobs | Reducing inventory systems costs by using robust demand estimators[END_REF]. A number of researchers investigated the related problem of unobserved lost sales and proposed efficient identification algorithms for relevant stochastic demand models [START_REF] Agrawal | Estimating negative binomial demand for retail inventory management with unobservable lost sales[END_REF][START_REF] Nahmias | Demand estimation in lost sales inventory systems[END_REF][START_REF] Tripathi | Estimation of parameters in the beta binomial model[END_REF]. However, no research has been reported on the performance of the Beta-Binomial Demand Model (BBM) in such settings. So, this paper focuses on the analysis of the Beta-Binomial Distribution-(BBD-) based forecasting risk and also proposes consistent estimators for the demand values, which are robust in respect to the distorted historical data. This paper also contributes in some neighbouring areas, such as implication of errors in survey data [START_REF] Gaba | Implications of errors in survey data[END_REF], where the data distortions may have an essential effect on inferences, such as too-high point estimates and too-narrow estimation intervals.

The remainder of the paper is organised as follows. Section 2 defines the general inventory optimisation problem and justifies applications of the GBBD. In Section 3, the BBM is described in detail and its main characteristics are presented. Section 4 focuses on minimisation of the forecasting risk and contains the main theoretical deliverables, such as the explicit expressions for the forecasting risk and the prediction function, which minimises the error impact on the risk. Section 5 contains simulation results. Section 6 describes an application example. Section 7 summarises the main contributions of this paper.

Inventory optimisation problem

A basic inventory optimisation problem can be stated as follows [START_REF] Grange | Challenges in modeling demand for inventory optimization of slow-moving items[END_REF]. Denote by m the number of SKU and let D l and Q l be the demand rate and stock guidance ('order-up-to' quantity) of the lth SKU over a fixed period of time (e.g. one week). Define the total fill rate as ( )

1 1 {} { } () {} m ll l l m l l E DPD Q fQ ED = = ≤ = (1)
where E{D l } is the expected demand for the lth SKU, P{D l ≤ Q l } is the individual service level of this SKU, and

Q = {Q 1 ,…, Q 2 , Q m }. Let C l be the cost of the item l.
Then the problem is to minimise the total inventory cost ensuring the target total fill rate F:

1 min, ( ) m ll Q l CQ f Q F = →≥ (2)
In order to solve problem (2) that is rather common for the combinatorial optimisation, one must know the probability distribution of the demand Dl for each SKU. Thus, this paper focuses on statistical aspects of the inventory optimisation, namely consistent estimation of the distribution parameters and minimisation of the forecasting risk with respect to the demand data distortions.

As was proved by [START_REF] Grange | Challenges in modeling demand for inventory optimization of slow-moving items[END_REF], an adequate demand model may be based on the BBD. An essential advantage of the BBM versus the classical Binomial Model (BM) is that the BBM takes into account possible correlation of the demand within a time period and between the periods, while the BM assumes that all requests are independent. The BBM also has some advantages over the Poisson-based models, which assumes only binary demand values and perform poorly for many industrial data sets [START_REF] Willemain | A new approach to forecasting intermittent demand for service parts inventories[END_REF]. In this paper, we apply a Generalisation of the Beta-Binomial Model (GBBM), proposed in our earlier research [START_REF] Dolgui | Modeling demand for inventory management of slow-moving items in case of reporting errors[END_REF].

Beta-binomial demand model

Let us assume that the demand data are arranged in an integer matrix {s ij , i = 1, …, k, i = 1, …, m}, where each observed value s ij is presented as a sum of n binary random variables

p p fp B α β π π α βππ ππ ππ -- - - = -- - (3)
where i denotes the item number (within a group of similar SKUs), j defines the observation period, n is the model parameter, (,)

B α β is the complete beta function; α, β and π 0 , π 1 are the shape and range distribution parameters respectively (0 ≤ π 0 < π 1 ≤ 1). This distribution takes into account the intermittent data nature by implicitly assuming that the observation time-segment may be uniformly divided in n time segments (an hour, a day, etc.), within which not more than one order can be received. It should be noted that such formulation follows the concept of the hierarchical (or mixed) statistical distributions where the probability of a random event is also treated as a random variable.

Under such assumptions, the generalised BBM may be expressed as the weighted sum of the shifted beta-binomial PDFs:

To obtain this expression, it is necessary to apply the linear transformation 0 p πθ =+ Δ with the standard-beta random variable [0, 1] θ ∈ and the width parameter 10 .

ππ Δ= -So, the marginal distribution of r may be presented as ( )

1 11 00 0 1 () ()( 1 ) d , rn r r n P r B α β πθ ρ θθ θ θ αβ -- - =+ Δ -Δ - (6)
where 00 1, Finally, the obtained sum of the integrals may be expressed via the beta-functions to yield (4), ( 5).

For computing convenience, the ratios of the beta-functions (, ) /

( ) ( ) 00 0 1 1 () 1 1 nn Vr V β α ππ ππ α β α β =+ - + - ++ (9)
where the first term

22 0 () ( ) ( 1 )

/

Vn n αβ α β α β α β =Δ + + + + + can be treated as the weighted variance of the standard BBD with the scale factor equal to the square range of p, and the remainder ones are the weighted variances of the binomial distribution with parameters π 0 , π 1 .

An essential feature of the GBBM is that it is capable of describing additive binary distortions in the demand records. As proved in our previous work [START_REF] Pashkevich | Robust modeling of consumer behavior[END_REF], to take into account distortions, the GBBM should be parameterised in the following way: π 0 = ε 0 and π 1 = 1-ε 1 , where ε 0 is the probability that a false order was erroneously recorded, and ε 1 is the probability that an order was wrongly omitted in the record.

Minimising forecasting risk

Traditionally, the demand probabilities are forecasted using the BBM Bayes predictor [START_REF] Collet | Modeling Binary Data[END_REF], which due to the conjugate property of the classical BBD is reduced up to () ( )/ ( ) , p ss n αα β =+ + + where , α β are the estimates of the BBM parameters, and s is the last observed demand value. This predictor minimises the mean square forecast error in the case of the consistent estimation of α, β. However, in the case of the data distortions, the classical predictor looses its optimality. Hence, a new predictor was developed, which minimises the forecasting risk in the case of the reporting errors.

It was proved [START_REF] Kharin | Statistical estimation of parameters for the beta-binomial distribution under distortions of binary observations[END_REF] that for the BBM with the reporting errors, the mean square optimal forecast obeys the following probability distribution ( )

11 01 0 1 ,, ( 1 ) (,
) the distribution shape parameters α, β only. Then, if the data are corrupted by the additive distortions with levels ε 0 , ε 1 , it is proved that the forecasting risk of the classical Bayes predictor is increased in accordance with the expression

n in i si i fp s p p Bi n i α β ε αβ +- + -- = =- ++ - (
( ) [ ] [2 ] [2 ] 2 [2 ] 2 00 1 1 22 01 0 2 2 2 2 () () ( ) () ( ) n n RR n n ε β εα βεε α ε βε αε αβαβ αβ αβ -+ + + -+ + =+ + ++ + ++ + (13)
where [] k α + and [] k α -denote the ascending/descending factorials of order k. Related proof is based on computing of the mean square error of the Bayes estimator taking into account the probability distributions (4), ( 11).

Since the distortions also influence the model parameter identification and α, β-estimators may produce non-consistent result, the forecasting risk is further increased. It was proved [START_REF] Pashkevich | Robust estimation and forecasting for beta-mixed hierarchical models of grouped binary data[END_REF] that in this case the forecasting risk can be minimised by using the proposed prediction function which in the case of relatively small error levels is approximated by the expression

α β αα ε α β α β ε α β ααε α β α β ε ++ - + - + - + - = ++- + + +- + - (14)
which is the product of the classical Bayes predictor and the correction factor depending on the error levels ε 0 , ε 1 . Application of the proposed robust predictor and its influence on the minimisation of the forecasting risk is illustrated in the following section.

Simulation study

To evaluate efficiency of the proposed forecasting and risk evaluation procedures, they were applied to a number of randomly generated data sets that originated from the beta-binomial demand distribution with parameters α = 0.5, β = 9.5, n = 10. Then, these data were contaminated by imposing the additive binary distortions with levels ε 0 , ε 1 ∈[0, 0.05]. Totally, 10,000 random samples were generated and used for both the model parameter estimation and demand value forecasting. Two basic cases were investigated based on the assumptions of the known and unknown distortion levels.

For the case of the known error levels, simulation results are shown in Figure 1,

where R denotes the forecasting risk and ε is the distortion level, assuming that ε 0 = ε 1 .

As follows from the figure, the distortions influence is non-negligible and they may cause essential increase of the forecasting risk. For instance, in the error-free case, the risk is equal to 0.046 while for ε = 0.05 the classical technique produces results with the risk about 0.071. In contrast, the proposed robust predictor yields 1.3 times better result, with the risk value of 0.054. It is comparable with the minimum possible bound defined by the Bayesian theory (only by 0.008 higher than the lower bound), that confirms the proposed method efficiency. In the case of the unknown distortion levels, the experimental data sets were first used for the identification of the error levels. Then, the estimates of ε 0 , ε 1 were passed on to the forecasting routine. The obtained results are also optimistic, while even theoretically they cannot be obviously as good as in the previous case because of the additional source of the uncertainty related to the stochastic distortions. As follows from the computer experiments, for ε = 0.05 the proposed estimation method (given in our previous paper, Dolgui et al., 2004) in combination with the prediction technique, proposed here, is able to reduce the forecasting risk down to 0.55. Hence, the developed forecasting method demonstrates a robust behaviour in respect to the data distortions, which is attractive for industrial applications.

Application example

To validate the efficiency of the developed forecasting method in real world settings, the demand data were used for two service parts reported by [START_REF] Snyder | Forecasting sales of slow and fast moving inventories[END_REF]. The review period was assumed to be one month, and values for 36 months were available.

The distribution parameters α, β and distortion levels ε 0 = ε 1 were estimated using the demand data for the first 24 months (for several values of n).

Since the demand values possess stable seasonality, the Bayes forecast for the third year (months 25-36) was generated using the corresponding month demand of the second year (months 13-24). Two types of the predictors were used: the classical Bayes and the developed ones. The performance of each forecast was evaluated by comparing the square root of the mean square forecast error, that is, the forecasting risk (R).

Tables 1 and2 present the actual demand for the months 25-36 and the forecast results for different values of the parameter n. It should be noted that the initial n-value is defined as the maximum demand in the past samples (months 1-24), and then it is slightly increased to consider the case of possible larger demand in the future. As follows from the tables, the proposed technique ensures essentially lower forecast error for the part 2, and a little lower error for part 1 when compared to the classical approach. As an example, for part 2, n = 8, the classical model leads to the error 1.72, while the proposed model ensures a value of 1.30 that results in 33% risk reduction. For the considered demand data, the risk sensitivity was also analysed with respect to the parameter n. As follows from relevant computations, the classical demand model is rather non-sensitive to selecting of n-value, while the generalised model (incorporating reporting errors) should be properly tuned to achieve the low value of the forecast risk.

In particular, it is prudent to define n close to the maximum demand in the learning sample, whereas unjustified increases of n may reduce the model efficiency. However, this complication in model tuning is compensated by reduction of the forecast risk.

Conclusion

Forecasting intermittent demand is a challenging problem of inventory management.

Current practice in such modelling favours the exponential smoothing of the demand values or applying exponential smoothing separately to the intervals between non-zero demands and their sizes (Croston's method). Alternatives recommended in inventory control literature are based on the bootstrap or Poisson distribution, which assumes exponential inter-arrival times. This paper describes another demand model, based on the generalised BBD, which is capable of incorporating the additive distortions as parameters. In combination with the Bayesian technique, this model is also able to describe the intermittent demand patterns with essentially non-exponential (poly-modal) distribution of the inter-arrival times. This paper contributes to the forecasting risk analysis in the presence of demand record errors, which are modelled as binary additive distortions that contaminate the actual demand data described by the generalised BBD. For this setting, explicit expressions were derived for the forecasting risk and the prediction function, which minimise the error impact. The efficiency of the proposed approach is confirmed by computer simulation and is illustrated by an application example for forecasting the intermittent demand values for car spare parts.

  where P r is the probability that the demand for the time-segment is equal to r, and the weights are expressed as

  w rl computed via the Binomial theorem.

[

  can be further simplified and Equation (4) can be rewritten as: approach with the dummy random variable θ, the demand mean E(r) can be expressed via the conditional expectation as 0 as the average non-zero/zero probabilities for the standard BBD-model. Similarly, the demand variance V(r) can be expressed via the conditional mean and variance as (of the conditional components and substitution of E(θ) and V(θ) one can obtain:

  related forecast risk, let us note that in the non-distorted data case the risk is computed from the expression

Figure 1

 1 Figure 1 Forecasting risk for classical and proposed predictor functions (theoretical curves and experimental 95% confidence intervals)

Table 1

 1 Forecasts for Service_Part #1 (classical and proposed predictors)

	Month Demand		n = 3	n = 4		n = 5		n = 6
			BBM	GBBM BBM GBBM BBM	GBBM	BBM	GBBM
	25	0	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	26	1	0.858 0.957	0.822 0.905	0.804	0.882	0.793	0.869
	27	1	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	28	2	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	29	2	0.858 0.957	0.822 0.905	0.804	0.882	0.793	0.869
	30	2	0.858 0.957	0.822 0.905	0.804	0.882	0.793	0.869
	31	1	1.374 1.477	1.212 1.292	1.132	1.202	1.083	1.148
	32	0	0.858 0.957	0.822 0.905	0.804	0.882	0.793	0.869
	33	0	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	34	2	1.374 1.477	1.212 1.292	1.132	1.202	1.083	1.148
	35	0	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	36	0	0.343 0.408	0.431 0.509	0.476	0.559	0.502	0.588
	Forecast risk	0.793 0.771	0.799 0.780	0.807	0.789	0.813	0.797

Table 2

 2 Forecasts for Service_Part #2 (classical and proposed predictors)

	Month Demand		n = 8		n = 9		n = 10	n = 11
			BBM	GBBM BBM	GBBM BBM	GBBM BBM	GBBM
	25	0	3.462 2.850	3.409	2.644	3.368	2.794	3.336 2.775
	26	0	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	27	1	4.139 3.754	4.055	3.534	3.990	3.803	3.937 3.558
	28	2	2.107 1.186	2.118	1.092	2.126	1.109	2.132 1.350
	29	1	0.752 0.393	0.826	0.391	0.883	0.405	0.929 0.544
	30	0	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	31	0	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	32	1	2.784 1.953	2.763	1.787	2.747	1.842	2.734 2.015
	33	0	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	34	0	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	35	1	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	36	1	1.430 0.674	1.472	0.642	1.504	0.654	1.531 0.857
	Forecast risk	1.724 1.295	1.717	1.209	1.712	1.287	1.709 1.278

Acknowledgements

The research is financially supported by the European Union grant INTAS YSF 03-55-869 and CODESNET coordination action.