Patent Publication Number: US-11658877-B2

Title: Optimum resource allocation and device assignment in a MEC cluster

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This patent application claims priority to and is a continuation of U.S. patent application Ser. No. 16/828,628, filed on Mar. 24, 2020, titled “Optimum Resource Allocation and Device Assignment in a MEC Cluster,” the disclosure of which is incorporated by reference herein in its entirety. 
    
    
     BACKGROUND INFORMATION 
     In order to satisfy the needs and demands of users of mobile communication devices, providers of wireless communication services continue to improve available services. One enhancement made possible through new broadband cellular networks is the use of Multi-access Edge Computing (MEC) clusters (also referred to as Mobile Edge Computing clusters). The MEC clusters allow high network computing loads to be transferred onto edge servers. Depending on the location of the edge servers relative to the point of attachment (e.g., a wireless station for a user device), MEC clusters can provide various services and applications to user devices with minimal latency, jitter, and loss. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    illustrates an exemplary network environment in which the concepts described herein may be implemented; 
         FIG.  2    depicts exemplary components of an exemplary network device; 
         FIG.  3    illustrates an exemplary functional components of the Multi-Access Edge Computing (MEC) cluster of  FIG.  1   ; 
         FIGS.  4 A and  4 B  show exemplary components of a table in the resource utilization database of  FIG.  3    according to one implementation; 
         FIG.  5    is a flow diagram of an exemplary process that is associated with allocation of resources from the MEC devices and the data center of  FIG.  1   , according to one implementation; 
         FIG.  6    is an exemplary graph of historical data and a future resource utilization value computed based on the historical data; and 
         FIG.  7    is a flow diagram of an exemplary process for predicting a future resource utilization value based on historical data and for selecting a MEC device to provide a service, based on the predicted value. 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     The following detailed description refers to the accompanying drawings. The same reference numbers in different drawings may identify the same or similar elements. 
     A MEC cluster is a collection of MEC devices. A service provider may implement a MEC cluster to provide faster services with less latency to a device, a user equipment (UE) device, and/or Internet-of-Things (IoT) device that is attached to the network. Each MEC cluster may be positioned geographically close to the serviced devices (also referred to herein as “devices.”). The close proximity of the MEC cluster reduces the average latency, jitter, and loss of the services rendered by the MEC cluster. 
     To ensure that MEC clusters render services with minimal latency, each MEC cluster is capable of handling heavy computational loads at high speeds. To allow the MEC clusters and devices to support attached device mobility or to provide service without abnormal latency, MEC clusters and devices need a mechanism to efficiently allocate and share resources for servicing the devices. For example, assume that a MEC cluster includes two MEC devices. A first of the MEC devices supports multiple devices and the second MEC device supports none. Also assume that the first MEC device is using 99% of its memory and 50% of its processing cycles to support the devices. When a roaming device attaches to the network in which the MEC cluster is located, the MEC cluster needs to assign the second MEC device to service the device and avoid overloading the first MEC device. 
     The systems and methods described herein relate to allocating MEC resources. Each MEC device may avoid rendering services with large latencies or being overloaded by evaluating when and how to share resources (e.g., Central Processing Unit (CPU) use, memory, port bandwidth, etc.) between the MEC devices and/or a remote data center. In addition, the MEC cluster or a remote data center may predict future utilization of MEC resources based on historical data, and determine on what MEC device an additional virtual network function (VNF) may be deployed based on the prediction. 
       FIG.  1    illustrates an exemplary network environment  100  in which the concepts described herein may be implemented. As shown in  FIG.  1   , environment  100  may include a provider network  102 , and devices in groups  112 - 1  through  112 -N. For simplicity,  FIG.  1    does not show all components that may be included in network environment  100  (e.g., routers, bridges, wireless access point, additional networks, additional devices, etc.). That is, depending on the implementation, network environment  100  may include additional, fewer, different, or a different arrangement of components than those illustrated in  FIG.  1   . 
     Provider network  102  may provide communications services (e.g., Internet Protocol (IP) services) to devices  112 . Provider network  102  may include a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), a radio access network, an optical network, a cable television network, a satellite network, a wireless network (e.g., a CDMA network, a general packet radio service (GPRS) network, an Long Term Evolution (LTE) network (e.g., a Fourth Generation (4G) network), a Fifth Generation (5G) network, an ad hoc network, a telephone network (e.g., the Public Switched Telephone Network (PSTN), an intranet, or a combination of networks. Provider network  102  may interface with other external networks, such as a packet data network or another provider network. 
     Provider network  102  may include an access network  104 , a core network  106 , MEC cluster  108 , a data canter  114 , and, in some embodiments, a separate MEC cluster management system. Access network  104  may allow a device  112  to access core network  106 . To do so, access network  104  may establish and maintain, with participation from devices  112 , an over-the-air channel with the devices  112 ; and maintain backhaul channels with core network  106 . Access network  104  may convey information through these channels, from the devices  112  to core network  106  and vice versa. 
     Access network  104  may include a Long-term Evolution (LTE) radio network and/or a 5G radio network or other advanced radio network. These radio networks may include many wireless stations, for establishing and maintaining an over-the-air channel with the devices  112 . 
     A wireless station in access network  104  may include a 4G, 5G, or another type of wireless station (e.g., eNB, gNB, etc.) that includes one or more radio frequency (RF) transceivers. Such a wireless station (also referred to as a base station) may provide or support one or more of the following: carrier aggregation functions; advanced or massive multiple-input and multiple-output (MIMO) antenna functions (e.g., 8×8 antenna functions, 16×16 antenna functions, 256×256 antenna functions, etc.); cooperative MIMO (CO-MIMO) functions; relay stations; Heterogeneous Network (HetNets) of overlapping small cell-related functions; macrocell-related functions; Machine-Type Communications (MTC)-related functions, such as 1.4 MHz wide enhanced MTC (eMTC) channel-related functions (i.e., Cat-M1), Low Power Wide Area (LPWA)-related functions such as Narrow Band (NB) Internet-of-Thing (NB-IoT) technology-related functions, and/or other types of MTC technology-related functions; Dual Connectivity (DC), and other types of LTE-Advanced (LTE-A) and/or 5G-related functions. In some implementations, a wireless station may be part of an evolved UMTS Terrestrial Network (eUTRAN). 
     In some implementations, wireless stations may include or be coupled to a MEC cluster  108  or a MEC device. Such a MEC cluster/device is geographically close to devices  112  that are attached to provider network  102  via the wireless station, and thus may be capable of providing services with a minimal latency, jitter and loss. 
     Core network  106  may include a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), an optical network, a cable television network, a satellite network, a wireless network (e.g., a CDMA network, a general packet radio service (GPRS) network, an LTE core network (e.g., a 4G network), a 5G core network, an ad hoc network, a telephone network (e.g., the Public Switched Telephone Network (PSTN), an intranet, or a combination of networks. Core network  106  may allow the delivery of IP services to devices  112 , and may interface with other external networks, such as a packet data network. In some implementations, core network  106  may include one or more MEC clusters  108 , although MEC clusters  108  are typically located at the edge of provider network  102 . 
     As further shown in  FIG.  1   , provider network  102  may include one or more MEC clusters  108 . Each MEC cluster  108  may provide services for devices  112  wirelessly attached to a base station in access network  104 . MEC cluster  108  may be in geographical proximity to the base station or at other edges of provider network  104 . As an example, MEC cluster  108  may be located on the same site as the base station. As another example, MEC cluster  108  may be geographically close to a 5G New Radio (NR) base station, and reachable via fewer network hops and/or fewer switches, than other base stations. As yet another example, MEC may be reached without having to interface with a gateway device, such as a 4G Packet Data Network Gateway (PGW) or a 5G User Plane Function (UPF). In some implementations, MEC cluster  108  may be located at customer premises, or at any other location to reduce latencies. 
     MEC cluster  108  may interface with access network  104  and/or with core network  106  via a MEC gateway device (not shown in  FIG.  1   ). In some implementations, MEC cluster  108  may be connected to access network  104  via a direct connection to a base station. In other implementations, MEC cluster  108  may include, or be included in, core network  106 . As an example, MEC cluster  108  may connect to a Session Management Function (SMF) or a UPF. MEC cluster  108  may support device mobility and handover application sessions between MEC cluster  108  and another MEC clusters. 
     MEC cluster  108  may support device registration, discovery, and/or management of MEC devices  110 - 1  through  110 -N in MEC cluster  108 . Each MEC device  110 -X (herein individually referred to as MEC device  110  or collectively as MEC devices  110 ) may service each corresponding group of devices  112 -X. For example, MEC device  110 - 1  services devices  112 - 1 . 
     MEC device  110  may include software components, such as an operating system, virtual machine, virtual container, application, and/or another type of software components or programs as further described below with reference to  FIG.  3   . MEC device  110  may be connected to a base station in access network  104  and may provide one or more MEC services to devices connected to the base station. As an example, a MEC service may include a service associated with a particular application. 
     Data center  114  may include various network devices and applications with storage and computing resources. In some embodiments, data center  114  may be implemented as a cloud platform (e.g., Verizon® cloud platform (VCP)) or another type of platform. When the MEC cluster  108  servicing a particular device  112  is overloaded, data center  114  may provide the necessary resources to service the device  112 . 
     As also shown in  FIG.  1   , network environment  100  includes groups  112 - 1  through  112 -N of devices. If an index J (not shown in  FIG.  1   ) denotes a particular group, then devices  112 -J 1  through  112 -Jm (where J≤N) belong to the group J. That is, devices  112 -J 1  through  112 -Jm are serviced by the corresponding MEC device  110 -J, through communication channels through the corresponding base station. For example, devices  112 - 11  . . .  112 - 1   m  are serviced by MEC device  110 - 1 . 
     Each device  112  (also referred to as UE device  112 ) may include a wireless communication device. Examples of device  112  include: a smart phone; a tablet device; a wearable computer device (e.g., a smart watch); a global positioning system (GPS) device; a laptop computer; a media playing device; an IoT device; and a portable gaming system. In some implementations, device  112  may correspond to a wireless Machine-Type-Communication (MTC) device that communicates with other devices over a machine-to-machine (M2M) interface, such as Long-Term-Evolution for Machines (LTE-M) or Category M1 (CAT-M1) devices and Narrow Band (NB)-IoT devices. Device  112  may send packets over or to provider network  102 . 
     In  FIG.  1   , each group  112  may include different or the same number of devices  112  than other groups  112 . Furthermore, each device  112  may require the MEC device  110  servicing the device  112  to use a different amount of computational resources. Thus, it is possible that one MEC device  110  is requested to allocate resources to service devices  112  at levels beyond which the MEC performance rapidly degrades (e.g., large latencies), while resources of MEC device  110  are underutilized. To prevent the preceding situation, an orchestrator of MEC cluster  108  or Data Center may perform resource management over its member devices  110 , as described below with reference to  FIGS.  3 - 7   . 
     Depending on the implementation, MEC devices  110  in MEC cluster  108  may be interconnected in a particular network topology. If MEC devices  110  that are in close proximity to each other are included in a cluster, each MEC device  110  would have two neighboring MEC devices  110 . Assuming that there are 5 MEC devices  110  in MEC cluster  108 , for example, and that MEC devices  110 - 1  and  110 - 5  are the MEC devices at the ends of the series, MEC device  110 - 2  would be a neighbor of MEC device  110 - 1 , MEC device  110 - 3  would be a neighbor of MEC device  110 - 2 , and so forth. 
     In  FIG.  1   , assume the computational cost of device  112 - 1 J accessing MEC device  110 - 1  is denoted by C D-MEC ; and the computational cost of a MEC device  110  accessing its neighbor is C MEC-MEC , where the computational cost may be memory, CPU cycles, bandwidth, physical links, etc. For simplicity, also assume that the computational costs of connectivity between any adjacent two MEC devices are the same and are represented by C MEC-MEC . The cost of device  112 - 1 J accessing MEC device  110 -N is then given by:
 
 C   D-MEC-N   =C   D-MEC +( N− 1)· C   MEC-MEC    (1)
 
Expression (1) reflects the fact that, a device  112 - 1 J that ends up accessing MEC device  110 -N would first connect to MEC device  110 - 1 , which would then hop through neighboring MEC devices  110 - 2  through  110 -N- 1  to reach MEC device  110 -N. Thus, expression (1) represents the worst-case scenario performance cost that does not involve accessing data center  114 . In many implementations, MEC cluster  108  may be designed to service devices  112  such that:
 
 C   D-REMOTE-MEC   ≤C   D-MEC-N−   =C   D-MEC +( N− 1)· C   MEC-MEC    (2)
 
Where C D-REMOTE-MEC  is the cost of accessing any one of the MECs other than MEC 1  for device  112 .
 
     In some implementations, in addition to satisfying expression (2), MEC cluster  108  may also satisfy the requirement that the actual computational cost of accessing an application on MEC device  110 -N is less than or equal to the computational cost of accessing another instance of the application on a remote data center  114  (C D-CP ).
 
 C   D-REMOTE-MEC   ≤C   D-CP    (3)
 
If a particular application that may be considered a resource or that accesses a resource is installed only at the remote data center  114 , MEC devices  110  need not satisfy expression (3). In many implementations, device  112  may access the data center  114  when there are not enough resources within MEC cluster  108 , since the data center  114  performance will be inferior to that of the MEC device  110  for rendering a service.
 
     In some implementations, MEC devices  110  may also satisfy the requirement:
 
RTD D-REMOTE-MEC ≤RTD D-CP    (4)
 
under certain utilization of MEC devices  110  in the MEC cluster  108 . In expression (4), RTD D-REMOTE-MEC  denotes the round trip delay for device  112 -IJ accessing MEC device  110 -L, and RT D-CP  is the round trip delay for device  112 -IJ accessing the data center  114 . In the expression (4), it is possible to use one-way delay instead of round trip delay between I 12 -IJ and MEC device  110 -L, and one-way delay between I 12 -IJ and the Data Center. If the memory utilization (E) and the CPU utilization (U) at MEC device  110 -L remain less than thresholds α and β, respectively, MEC device  110 -L may continue to service device  112 -LJ.
 
       FIG.  2    depicts exemplary components of an exemplary network device  200 . Network device  200  may correspond to or may be included in any of network components of  FIG.  1    (e.g., MEC devices  110 , devices  112 , a router, a network switch, servers, gateways, etc.). As shown, network device  200  may include a processor  202 , memory/storage  204 , input component  206 , output component  208 , network interface  210 , and communication path  212 . In different implementations, network device  200  may include additional, fewer, different, or a different arrangement of components than the ones illustrated in  FIG.  2   . For example, network device  200  may include a display, network card, etc. 
     Processor  202  may include a processor, a microprocessor, an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), programmable logic device, chipset, application specific instruction-set processor (ASIP), system-on-chip (SoC), central processing unit (CPU) (e.g., one or multiple cores), microcontrollers, and/or other processing logic (e.g., embedded devices) capable of controlling device  200  and/or executing programs/instructions. 
     Memory/storage  204  may include static memory, such as read only memory (ROM), and/or dynamic memory, such as random access memory (RAM), or onboard cache, for storing data and machine-readable instructions (e.g., programs, scripts, etc.). 
     Memory/storage  204  may also include a floppy disk, CD ROM, CD read/write (R/W) disk, optical disk, magnetic disk, solid state disk, holographic versatile disk (HVD), digital versatile disk (DVD), and/or flash memory, as well as other types of storage device (e.g., Micro-Electromechanical system (MEMS)-based storage medium) for storing data and/or machine-readable instructions (e.g., a program, script, etc.). Memory/storage  204  may be external to and/or removable from network device  200 . Memory/storage  204  may include, for example, a Universal Serial Bus (USB) memory stick, a dongle, a hard disk, off-line storage, a Blu-Ray® disk (BD), etc. Memory/storage  204  may also include devices that can function both as a RAM-like component or persistent storage, such as Intel® Optane memories. 
     Depending on the context, the term “memory,” “storage,” “storage device,” “storage unit,” and/or “medium” may be used interchangeably. For example, a “computer-readable storage device” or “computer-readable medium” may refer to both a memory and/or storage device. 
     Input component  206  and output component  208  may provide input and output from/to a user to/from device  200 . Input/output components  206  and  208  may include a display screen, a keyboard, a mouse, a speaker, a microphone, a camera, a DVD reader, USB lines, and/or other types of components for obtaining, from physical events or phenomena, to and/or from signals that pertain to device  200 . 
     Network interface  210  may include a transceiver (e.g., a transmitter and a receiver) for network device  200  to communicate with other devices and/or systems. For example, via network interface  210 , network device  200  may communicate over a network, such as the Internet, an intranet, a terrestrial wireless network (e.g., a WLAN, WiFi, WiMax, etc.), a satellite-based network, optical network, etc. 
     Network interface  210  may include an Ethernet interface to a LAN, and/or an interface/connection for connecting device  200  to other devices (e.g., a Bluetooth interface). For example, network interface  210  may include a wireless modem for modulation and demodulation. 
     Communication path  212  may enable components of network device  200  to communicate with one another. 
     Network device  200  may perform the operations described herein in response to processor  202  executing software instructions stored in a non-transient computer-readable medium, such as memory/storage  204 . The software instructions may be read into memory/storage from another computer-readable medium or from another device via network interface  210 . The software instructions stored in memory/storage (e.g., memory/storage  204 , when executed by processor  202 , may cause processor  202  to perform processes that are described herein. 
       FIG.  3    illustrates exemplary functional components of MEC cluster  108  of  FIG.  1   . As noted above, MEC cluster  108  may include one or more MEC devices  110 , each of which may include one or more network devices  200  that are configured to implement the functional components as hardware or software. The functional components may be part of software programs or modules. As shown, the functional components may include a cluster orchestrator  302 , a device registry  304 , a performance monitor  306 , a resource utilization database  308 , and machine learning logic  310 . 
     Cluster orchestrator  302  may include logic for instantiating, terminating, and/or scheduling application and service processes, depending various constraints and parameters, such as priorities. For example, cluster orchestrator  302  may receive instructions from a network operator to start or end certain service and/or application processes, modify their priorities, and/or schedule their execution at particular virtual/physical hardware. In another example, cluster orchestrator  302  may obtain process-related instructions from an administrator program (e.g., a program running on a remote device) or from stored instructions. In yet another example, cluster orchestrator  302  may create instances of programs that include performance monitor  306  and machine learning logic  310 . 
     Cluster orchestrator  302  may also assign hardware resources, to service specific devices  112 , based on outputs from performance monitor  306 , information in device registry  304  and data in resource utilization database  308 . Additionally, cluster orchestrator  302  may assign a particular MEC device  110  to service a device  112  based on outputs from machine learning logic  310  and data in resource utilization database  308 . Processes that cluster orchestrator  302  perform for MEC resource allocation and MEC device  110  assignment are described below with reference to  FIGS.  5 - 7   . 
     Device registry  304  may include information pertaining to each of MEC devices  110 . To perform many of its functions, cluster orchestrator  302  needs a list of MEC devices  110 . Device registry  304  stores and maintains such a list. Typically, device registry  304  may include identifiers for MEC devices  110  (e.g., Media Access Control (MAC) address, IP address, etc.), for hardware components (e.g., memory, CPUs, network interfaces, etc.), and/or for other device-related information (e.g., what software components are installed at MEC devices  110 ). When a MEC device  110  is brought online and becomes part of MEC cluster  108 , cluster orchestrator  302  registers the MEC device  110  at registry  304 , populating registry  304  with data pertaining to the MEC device  110 . Conversely, if MEC device  110  is removed from MEC cluster  108 , cluster orchestrator  302  de-registers MEC device  110 , removing the data from registry  304 . Examples of registry information includes: the amount of RAM for each MEC device  110 ; the number of CPUs, identifiers associated with each CPU, and the CPU speeds; the number of network interfaces and their bandwidths; a list of software components installed at MEC devices  110 ; etc. 
     Device registry  304  may also include a cluster identifier that uniquely identifies the cluster  108 . There may be more than one MEC cluster  108  in network  102 , and in such instances, provider network  102  may include a MEC orchestrator that oversees the clusters. The MEC orchestrator may provide a cluster ID to cluster orchestrator  302 , which would then store the cluster ID in device registry  304 . 
     Device registry  304  may also store network configuration information. For example, registry  304  may indicate the network topology of MEC cluster  108  (e.g., star, ring, etc.). In one implementation, MEC devices  110  may be interconnected as a ring; each MEC device  110  is connected to one MEC device  110  to its left and one MEC device  110  to its right. In another implementation, MEC devices  110  may be arranged in a line: except for two MEC devices  110  at the ends of the line, each MEC device  110  is connected to one MEC device  110  to its left and one MEC device  110  to its right. Device registry  304  may identify, for each MEC device  110  in registry  304 , to what other devices the MEC device  110  is connected. 
     Performance monitor  306  may track resource utilization and performance data for each MEC device  110 . To monitor resource utilization for each MEC devices  110 , performance monitor  306  may issue system-level calls to hardware management programs (e.g., Operating System (OS)) on each MEC device  110 . When the programs return values of parameters indicating the amounts of resources in use, performance monitor  306  may store the returned values in database  308 . 
     Resource utilization database  308  may store values of parameters that performance monitor  306  obtains from MEC devices  110 . In some implementations, database  308  may be updated periodically or at scheduled times. 
     Machine learning logic  310  may use values of parameters, to obtain (or learn) the coefficients of a set of linear equations for predicting a future value of the parameter. Machine learning logic  310  may be used by cluster orchestrator  302  to predict the future use of a particular resource, and to assign a MEC device  110  to a VNF (Virtual Network Function) based on the prediction. 
     Depending on the implementation, MEC cluster  108  may include additional, fewer, or different functional components than those illustrated in  FIG.  3   . Furthermore, some of the components (or similar components) may be included in other components of provider network  104 , such as data center  114 , to provide services or resources to devices  112  when MEC devices  110  determines that they are unable to meet the required performance constraints. 
       FIGS.  4 A and  4 B  show exemplary components of a table in resource utilization database  308  according to one implementation. As shown, database  308  may include a table with records  402 . Each record  402  may include a cluster identifier (ID) field  404 , a device ID field  406 , a time stamp field  408 , a CPU/MEM field  410 , an RTD field  412 , a bandwidth (BW) field  414 , and a link cost field  416 . 
     Cluster ID field  404  may store an identifier that is associated with the cluster. The cluster ID may have been provided to cluster orchestrator  302  by a MEC orchestrator. Device ID field  406  may store an identifier that uniquely identifies the MEC device  110  in the cluster. The identifier may be an IP address, a MAC address, or another type of identifier. 
     Time stamp field  408  may store a timestamp that indicates the time at which one or more resource utilization parameter values are obtained and stored in database  308 . The time may be expressed as a number of seconds or milliseconds that elapsed since a particular epoch (e.g., Jan. 1, 1970). 
     CPU/MEM field  410  may include the amount of memory or percentage of CPU cycles when the timestamp value was obtained. In one implementation, CPU utilization may be indicated as a percent of total CPU cycles per second, and, memory utilization may be indicated in megabytes, terabytes, percent of the total available RAM, etc. 
     RTT field  412  may indicate an average round trip time for a packet issued from a particular device  112  to the MEC device  110  identified in device ID field  406 . Although  FIG.  4 B  shows RTT field  412  as having only a single RTT value for a corresponding device  112  (whose IP address is shown), in other implementations, RTT field  412  may include additional RTT values. Each of such RTT values may correspond to a device  112  that MEC device  110  services. 
     BW field  414  may include a list of ports/interfaces and their corresponding used or available bandwidth. Link cost field  416  may indicate a computational cost associated with a link. Depending on the implementation, the cost may be given in terms of an amount of specific resource used, for accessing another MEC device  110 . For example, link cost field  416  may indicate the cost for connecting to another MEC device  110  to its right, or to another MEC device  110  to its left and accessing its memory. In other examples, the cost may be a round trip delay, additional memory utilization, CPU cycles, etc. for accessing another MEC device  110 . 
     Depending on the implementation, record  402  may include additional, fewer, or different fields than those illustrated in  FIGS.  4 A and  4 B . For example, in one implementation, record  402  may not include a cluster ID field  404 , and in another implementation, record  402  may include a list of devices  112  serviced by the MEC device  110 . 
       FIG.  5    is a flow diagram of an exemplary process  500  that is associated with allocation of resources from MEC devices  110  and data center  114 , according to one implementation. Cluster orchestrator  302  may perform process  500  for a particular MEC device  110 - 1 , which may be a default MEC device for providing a particular service or the current MEC device  110  providing a service that needs additional resource. 
     As shown, process  500  may include determining whether the amount of memory (E) used at MEC device  110 - 1  exceeds a threshold (a) or the CPU utilization (U) exceeds another threshold (β) (block  502 ). That is, cluster orchestrator  302  may determine whether E&gt;α and/or U&gt;β. In one implementation, the determination may be triggered by an event that requires a new process, thread, additional memory, etc (e.g., a service request from device  112 ), etc. In another implementation, the determination may be triggered by a separate thread or a process that checks resource utilization at the MEC device  110  at regular time intervals. The determination may be made, for example, by examining the contents of CPU/MEM field  410  of record  402  in resource utilization database  308  or inspecting outputs from performance monitor  306 . 
     If E≤α and U≤β (block  502 : NO), cluster orchestrator  302  may allow the current MEC device  110  to handle the service (block  504 ). Otherwise (block  502 : YES), cluster orchestrator  302  may determine whether there exists a candidate MEC device  110  that can provide the resource (e.g., a MEC device  110  that is a neighbor of MEC device  110 - 1 ) (block  506 ). If there is no candidate MEC device  110  (block  506 : NO), cluster orchestrator  302  may direct the requested service to data center  114  (block  510 ), provided that expression (4) is satisfied. 
     If there is an available candidate MEC device  110  (block  506 : YES), cluster orchestrator  302  may examine memory utilization and CPU utilization for the candidate MEC device  110  (block  508 ), and determine, based on the data (obtained from database  308  or performance monitor  306 ), whether the candidate MEC device  110  meets constraints (block  512 ). For example, cluster orchestrator  302  may determine whether the candidate MEC device  110  meets the criteria: E CANDIDATE ≤α and U CANDIDATE ≤β, and B CANDIDATE ≤γ, where E CANDIDATE , U CANDIDATE , B CANDIDATE , and γ denote memory utilization, CPU utilization, port bandwidth utilization, and a bandwidth use threshold at the candidate MEC device  110 . 
     If the MEC device  110  meets the constraints (block  512 : YES), cluster orchestrator  302  may select the candidate MEC device  110  to provide the requested service or resource (block  514 ). Otherwise (block  512 : NO), cluster orchestrator  302  may return to block  506  to consider whether another candidate MEC device  110  is available. 
     For process  500  it is assumed that α, β, and γ are the same for all MEC devices  110  in cluster  108 . However, in a different implementation, resource utilization database  308  may store individualized memory, CPU, and port bandwidth threshold values for each MEC device  110 . In such implementations, cluster orchestrator  302  may use the individualized threshold values for each MEC device  110  in determining whether to access the MEC device  110 , for more precise resource allocation. 
     As indicated above, in addition to determining whether to allocate a resource from a MEC device  110 , cluster orchestrator  302  may also predict future resource utilization based on historical data. Such predictions may be used for MEC capacity planning as well as for assigning MEC devices  110  for VNFs (i.e., run a VNF on a selected MEC device  110 ). 
       FIG.  6    is an exemplary graph of historical data and a future resource utilization value computed based on the historical data.  FIG.  6    also illustrates the concept behind predicting the resource utilization value. In  FIG.  6   , historical data for resource utilization at a MEC device  110  is plotted for times at which the data were collected. More specifically, y 0 , y 1 , and y 2  are measured resource utilization values at times t 0 , t 1 , and t 2 . To predict the future resource utilization, cluster orchestrator  302  determines a curve  602  that best fits the historical data, and looks up (or interpolates) the value of curve  602  at t p , the time for which cluster orchestrator  302  needs to predict the resource utilization value. As shown in  FIG.  6   , the value is y p . Once y p  has been determined for each MEC device  110 , cluster orchestrator  302  may use the determined values to identify MEC devices  110  that are least used, and select the least used MEC devices  110  to provide a resource of a service (e.g., a VNF). 
       FIG.  7    is a flow diagram of an exemplary process  700  for predicting a future resource utilization value based on historical data and for selecting a MEC device  110  to provide a service, based on the predicted value. Depending on the implementation, process  700  may be performed by cluster orchestrator  302  or another program running on one of MEC devices  110  in cluster  108 . 
     As shown, process  700  may include collecting resource utilization data (block  702 ). For example, cluster orchestrator  302  may start and run performance monitor  306 , which, in turn, may collect resource utilization data from MEC devices  110  and store the collected data in database  308 . After the data has been collected, to predict a future resource utilization value, cluster orchestrator  302  may select an appropriate time window during which historical data has been collected (block  704 ). In addition, cluster orchestrator  302  may select data points, within the time window, obtained at specific times (e.g., every 5 minutes, every 10 minutes, every 15 minutes, etc.). Cluster orchestrator  302  may use the selected data within the time window for predicting the resource utilization value at a particular time t. 
     In one implementation, to predict the utilization value, cluster orchestrator  302  uses the selected data for machine learning. The machine learning is based on a mathematical relationship between resource utilization values y 0 , y 1 , y 2  . . . and y p  and times t 0 , t 1 , t 2  . . . and t p  at which the values were obtained. The relationship can be written as:
 
 y   r   ≅y   0   +T   r   T   ·W    (5)
 
     T r  and W are defined as: 
               T   r     =         [           t   1               t   2             ⋮             t   r           ]     ⁢           ⁢   and   ⁢           ⁢   W     =       [           w   1               w   2             ⋮             w   r           ]     .             
In expression (5), W is the unknown vector being solved for and T r   T  is a transpose of T r . In this implementation, “machine learning” entails solving for the values of W. To solve for W, form the Least Squares Cost function based on expression (5) as follows:
 
                     G   ⁡     (   W   )       =       ∑     r   =   1     p     ⁢       (       y   0     ⁢           +       T   r   T     ⁢   W     -     y   r       )     2               (   6   )               
The cost function G(W) can be minimized by selecting the weights W. To select the weights, solve:
 
∇ G ( W )=0   (7)
 
∇G(W) is the gradient of G(W). Taking partial derivatives of G(W) using expression (6) to obtain the gradient, and then using expression (7) yields:
 
                     ∇     G   ⁡     (   W   )         =       2   ⁢       ∑     r   =   1     p     ⁢       T   r     ⁡     (       y   0     ⁢           +       T   r   T     ⁢   W     -     y   r       )           =   0             (   8   )               
Expression (8) can be rewritten as:
 
     
       
         
           
             
               
                 
                   
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         p 
                       
                       ⁢ 
                       
                         
                           T 
                           r 
                         
                         ⁢ 
                         
                           y 
                           0 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         P 
                       
                       ⁢ 
                       
                         
                           T 
                           r 
                         
                         ⁢ 
                         
                           T 
                           r 
                           T 
                         
                         ⁢ 
                         W 
                       
                     
                     - 
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         p 
                       
                       ⁢ 
                       
                         
                           T 
                           r 
                         
                         ⁢ 
                         
                           y 
                           r 
                         
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     Cluster orchestrator  302  may solve equation (9) to obtain W (i.e., values of w 1 , w 2  . . . and w p ). Solving for W yields: 
     
       
         
           
             
               
                 
                   W 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             P 
                           
                           ⁢ 
                           
                             
                               T 
                               r 
                             
                             ⁢ 
                             
                               T 
                               r 
                               T 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             p 
                           
                           ⁢ 
                           
                             
                               T 
                               r 
                             
                             ⁢ 
                             
                               y 
                               r 
                             
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             p 
                           
                           ⁢ 
                           
                             
                               T 
                               r 
                             
                             ⁢ 
                             
                               y 
                               0 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     Once W is obtained, cluster orchestrator  302  may use a version of the following expression (11) to compute y t . The expression is:
 
 y   t   ≅y   0   +T   t   T   ·W    (11)
 
T t  in expression (11) is defined as T r  at t 0 =t 1 =t 2  . . . t r =t. That is:
 
               T   t     =       [         t           t           ⋮           t         ]     .           
Using expression (11), cluster orchestrator  302  may predict the resource utilization y t  at time t based on the data (block  708 ).
 
     In the above, expressions (5)-(11) deal with the situation where the outputs are assumed to be linear. For a non-linear case,
 
 y   r   ≅y   0   +F   r   T   ·W    (12)
 
where
 
               F   r     =         [           f   ⁡     (     t   1     )                 f   ⁡     (     t   2     )               ⋮             f   ⁡     (     t   r     )             ]     ⁢           ⁢   and   ⁢           ⁢   W     =       [           w   1               w   2             ⋮             w   r           ]     .             
Each f(t) can be a sinusoidal function, such as sin(2π t r ). To solve for W, form the Least Squares Cost function based on expression (12) similarly as above:
 
                     G   ⁡     (   W   )       =       ∑     r   =   1     p     ⁢       (       y   0     ⁢           +       F   r   T     ⁢   W     -     y   r       )     2               (   13   )               
As before, find ∇G(W) by taking partial derivatives of G(W) and set it equal to zero to obtain:
 
                     ∇     G   ⁡     (   W   )         =       2   ⁢       ∑     r   =   1     p     ⁢       F   r     ⁡     (       y   0     ⁢           +       F   r   T     ⁢   W     -     y   r       )           =   0             (   14   )               
Expression (14) can be rewritten as:
 
     
       
         
           
             
               
                 
                   
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         p 
                       
                       ⁢ 
                       
                         
                           F 
                           r 
                         
                         ⁢ 
                         
                           y 
                           0 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         P 
                       
                       ⁢ 
                       
                         
                           F 
                           r 
                         
                         ⁢ 
                         
                           F 
                           r 
                           T 
                         
                         ⁢ 
                         W 
                       
                     
                     - 
                     
                       
                         ∑ 
                         
                           r 
                           = 
                           1 
                         
                         p 
                       
                       ⁢ 
                       
                         
                           F 
                           r 
                         
                         ⁢ 
                         
                           y 
                           r 
                         
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     Cluster orchestrator  302  may solve equation (9) to obtain W (i.e., values of w 1 , w 2  . . . and w p ). Solving for W yields: 
     
       
         
           
             
               
                 
                   W 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             P 
                           
                           ⁢ 
                           
                             
                               F 
                               r 
                             
                             ⁢ 
                             
                               F 
                               r 
                               T 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             p 
                           
                           ⁢ 
                           
                             
                               F 
                               r 
                             
                             ⁢ 
                             
                               y 
                               r 
                             
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               r 
                               = 
                               1 
                             
                             p 
                           
                           ⁢ 
                           
                             
                               F 
                               r 
                             
                             ⁢ 
                             
                               y 
                               0 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     Once W is obtained, cluster orchestrator  302  may use a version of the following expression (17) to compute y t . The expression is:
 
 y   t   ≅y   0   +F   t   T   ·W    (17)
 
F t  in expression (17) is defined as F r  at t 0 =t 1 =t 2  . . . t r =t. That is:
 
     
       
         
           
             
               F 
               t 
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         f 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         f 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                   
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         f 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
     
     In process  700 , the predicted utilization y t  depends on the resource utilization data (i.e., y 0 , y 1 , y 2 , etc.) and the times at which the data were collected by performance monitor  306 . For example, assume that performance monitor  306  makes measurements 5 minutes apart (i.e., t 0 =0, t 1 =5, t 2 =10 . . . in minutes). Cluster orchestrator  302  may then use the above expressions (5)-(10) to determine y t  at t=20 minutes from the start. In another example, the time measurements may be one day apart (e.g., t 1 =1, t 2 =2 . . . in days). The data may be used to predict the resource utilization for the next 5 days. Other time intervals may be used (e.g., monthly, quarterly, etc.). 
     If performance monitor  306  measures resource utilization every minute, and creates sets of 5 minute or 10 minute (or any predetermined period) historical measurements (e.g., average resource utilization values, maximum resource utilization values, etc.). Database  308  may include such measurements for a certain time interval in a day (e.g., 9 a.m.-3 p.m., 3 p.m.-6 p.m., etc.) and use. Cluster orchestrator  302  may use the measurements to predict resource use for the same time interval in another day. 
     Returning to  FIG.  7   , cluster orchestrator  302  may determine which MEC device  110  to provide a resource (block  710 ). For example, cluster orchestrator  302  may use the preceding part of process  700  to install or instantiate a virtual network function (VNF) at a selected MEC device  110 . More specifically, assume that y p  represents how many times a specific VNF is accessed for different time slots. Depending on the predicted VNF access number, cluster orchestrator  302  may assign the next VNF instance to a particular MEC device  110  (e.g., at a MEC device with a low predicted VNF access count). In another example, if cluster orchestrator  302  predicts that resource utilization at all MEC devices  110  in cluster  108  will be over their thresholds, cluster orchestrator  302  may indicate a need for additional hardware (e.g., additional MEC device  110 , additional network ports, more RAM for MEC devices  110 , etc.). 
     In this specification, various preferred embodiments have been described with reference to the accompanying drawings. It will be evident that modifications and changes may be made thereto, and additional embodiments may be implemented, without departing from the broader scope of the invention as set forth in the claims that follow. The specification and drawings are accordingly to be regarded in an illustrative rather than restrictive sense. 
     It will be apparent that aspects described herein may be implemented in many different forms of software, firmware, and hardware in the implementations illustrated in the figures. The actual software code or specialized control hardware used to implement aspects does not limit the invention. Thus, the operation and behavior of the aspects were described without reference to the specific software code—it being understood that software and control hardware can be designed to implement the aspects based on the description herein. 
     Further, certain portions of the implementations have been described as “logic” that performs one or more functions. This logic may include hardware, such as a processor, a microprocessor, an application specific integrated circuit, or a field programmable gate array, software, or a combination of hardware and software. 
     To the extent the aforementioned embodiments collect, store or employ personal information provided by individuals, it should be understood that such information shall be collected, stored, and used in accordance with all applicable laws concerning protection of personal information. The collection, storage and use of such information may be subject to consent of the individual to such activity, for example, through well known “opt-in” or “opt-out” processes as may be appropriate for the situation and type of information. Storage and use of personal information may be in an appropriately secure manner reflective of the type of information, for example, through various encryption and anonymization techniques for particularly sensitive information. 
     No element, block, or instruction used in the present application should be construed as critical or essential to the implementations described herein unless explicitly described as such. Also, as used herein, the articles “a,” “an,” and “the” are intended to include one or more items. Further, the phrase “based on” is intended to mean “based, at least in part, on” unless explicitly stated otherwise.