Fog computing provides a distributed infrastructure at the edge of the network, resulting in low-latency access and faster response to application requests. omputing requirements of mobile users continue to increase, as computing and communication capabilities of smart and wearable devices and in-vehicle systems continue to improve. Many applications rely on remote resources to off-load and complete tasks, primarily through the use of a large-scale computing facility hosted within a data center. Such cloud systems are also able to support applications by storing data M A R C H /A P R I L 2 0 1 7 I E E E C LO U D CO M P U T I N G 2 7 and processing tasks offloaded by mobile or fixed devices. With increasing focus on Internet-of-Things (IoT), countless devices scattered and connected to the Internet, producing and consuming data requires scalable resource management at unprecedented levels. 1 The data dynamism and heterogeneity resulting from this expected explosive expansion of connected devices, commonly referred in a broad sense as Big Data, also requires new processing models and infrastructures to support its main dimensions: data volume, velocity, and variety. One key aspect of this new era is that both data consumption and production are heavily distributed and at the edges of the network (i.e. closer to or at end-user devices). While the centralized data center model of cloud computing can cope with many types of applications and large amounts of data, its infrastructure and network connection to the edge are not designed to handle this Big Data phenomenon. In this context, computing and data management models that support computing capacity at the edges of the network are now a focus of significant research. Mobile clouds, vehicular networks, and fog computing are examples of new distributed computing models that leverage edge capacity closer to data production. With data also produced at the edge, both data generation and consumption can occur at many different places and times. In this context, different applications can have different requirements, especially in terms of response time. Currently, applications often rely on the cloud to have data and processing support, which may not be suitable for lower latency requirements. Moreover, execution of applications in cloud data centers does not take user mobility into consideration, and data or processing of an application can occur at a geographically distant data center. On the other hand, in a distributed computing scenario at the edges of the network, data distribution and processing can be maintained closer to the user, reducing network traffic to data centers and improving application response times as a result of lower network latency or delay. This paper discusses the problem of resource allocation considering the hierarchical infrastructure composed of edge capacity and cloud data centers, analyzing application classes along with different scheduling policies. To address this challenge, we introduce a number of scheduling approaches that consider user mobility and edge computing capacity, in the context of a Fog Computing infrastructure. 1 We discuss the benefits of combining the application classes with scheduling policies in scenarios that illustrate these scheduling approaches, especially in the context of user mobility. The next section presents the fog computing model considered in this paper and then related work is discussed. Next, we introduce the application model and two example applications, which are used in the evaluation further in the paper. After that, we present different allocation policies and simulation results. Then, we discuss resource allocation challenges for fog computing. User applications that access the public cloud do so through an access point that allows data exchange through the core network to reach the cloud data center. With the introduction of computing capacity at the edge of the network, these access points can be extended to also provide computing and storage services: the cloudlets. Figure 1 illustrates the cloudlets concept within the hierarchical infrastructure of the fog. This fog computing architecture presents a hierarchical, bi-directional computing infrastructure: edge devices communicate with cloudlets and cloudlets communicate with clouds. Cloudlets can also 28 communicate with each other to perform data and process management in order to support application requirements, and to exchange fog control/management data (such as user device and application state). In fog computing, processing and storage capacity is one hop away from the data production/consumption, which can benefit different types of applications • Applications with low latency requirements, such as pedestrian and traffic security, surveillance, applications for vision, hearing, or mobilityimpaired users, online gaming, augmented reality, and tactile computing can benefit from lower latencies because of a single hop connection to a cloudlet. • Applications that currently rely on the cloud can also benefit from lower delays and response times when adopting a fog-based deployment if their data and processing is carried out by a nearby cloudlet. This can also reduce data traffic to the cloud. • Raw data collected by many devices often does not need to be transferred to the cloud for longterm storage: data can be processed, filtered, or aggregated to extract knowledge and produce reduced data sets, which in turn are to be stored; or it can be processed and utilized right-away to other edge devices in the so-called sensor/actuator loop. In both cases, the fog computing paradigm can reduce network traffic from the edge to data centers. Cloudlets can provide reduced latencies and help in avoiding/reducing traffic congestion in the network core. However, this comes at a price: more complex and sophisticated resource management and scheduling mechanisms are needed. This raises new challenges to be overcome, e.g., dynamically deciding what, when, and where (device/fog/cloud) to carry out processing of requests to meet their quality of service requirements. Furthermore, with smart and wearable devices, such mechanisms must incorporate mobility of data sources and sinks in the fog. Traditional resource management and scheduling models for distributed systems do not consider mobility and timeliness of data production and consumption in the resource management and allocation process. Fog computing scheduling must bring users location to the resource allocation policies to uphold the benefits of fog computing proximity to the user. Resource management and scheduling in fog computing is a new topic that combines aspects from sensor networks, cloud computing, mobile computing, and pervasive computing fields. In fog computing, sensors and other devices pervasively present at the edge of the fog generate data and consume data that have to be processed using the cloudlets and the clouds. Each of those fields has a plethora of literature, well documented by researchers. 3, 4, 5 Fog computing has been discussed as a platform to provide support for Internet of Things (IoT) and analytics. Bonomi et al. discuss many aspects of a fog infrastructure, including the interplay between fog and cloud systems. The authors claim that fog computing can better address applications and services that do not fit well in the cloud, such as low-latency or geo-distributed applications. In this paper, we advance this discussion by introducing strategies that can be adopted in the presence of different application classes. A programming model has been proposed to support fog computing applications, which includes event handlers and an application programming interface (API). 6 Programming models are complementary to the presented work, as they rely in application scheduling strategies to decide where to allocate the functions created by users. GigaSight is a virtual machine-based cloudlet infrastructure used to support video storage analytics at the edge. 7 One motivation for the proposal is to avoid overwhelming metropolitan networks with a large amount of video streams sent to cloud providers. GigaSight applications can share the cloudlets with other types of applications, where a proper resource allocation can improve performance. Jennings and Stadler 3 discuss resource management objectives and challenges in cloud computing. Many aspects are covered by them, including resource management functions and network-aware resource allocation, which are also relevant to fog computing. Edge devices in the fog introduce particularities that must be considered, among which application requirements and mobility are discussed in the remainder of this paper. Multi-clouds are platforms that aggregate computing resources from different cloud providers. While multi-clouds can help in decreasing latencies to the final users, they are not able to provide really low latencies as the ones advocated by fog computing with its 1-hop away cloudlet infrastructure. Thus, the hierarchical combination of fog and clouds (stand alone or federated) still offers advantages in terms of latency and network traffic. The European Telecommunications Standards Institute (ETSI) has launched the Mobile-Edge Computing (MEC) initiative to create standards for mobile edge computing platforms, having proposed a blueprint 9 and also documents presenting technical requirements, terminology, and service scenarios. A first specification is expected to be delivered by the end of 2016. In terms of resource allocation and scheduling, offloading decision in mobile devices is important. 5 Kosta et al. present ThinkAir, a framework to offload mobile applications to the cloud. 10 ThinkAir is able to parallelize execution using virtual machines, achieving reduced execution times and energy consumption in the mobile device. In a fog computing scenario, the offloaded modules should be allocated according to the application requirements, as we discuss further in this paper. The fog architecture is hierarchical, where processing and storage location decision is subject to application constraints and user geo-location. While the former can be specified in different ways, as in the form of quality of service (QoS) constraints, the latter depends on human (or other autonomous system) behavior. Ultimately, user behavior determines the time and position of a computing device, which along with QoS constraints can be used to create application classes that are relevant for resource management and scheduling in a fog computing environment. By acknowledging different application classes, one could employ different scheduling policies, algorithms, or mechanisms to deal with each class. To illustrate how resource management in fog computing can benefit applications by considering geolocation and different application classes, we identify two types of apps: near real-time and delay-tolerant. For the former, we describe the electroencephalography (EEG) tractor beam game; for the latter, a video surveillance/object tracking application. In the EEG tractor beam game (EEGTBG), players try to gather items by concentrating on them. A player that has a better concentration on an item can attract it towards him/herself. Fast processing and low response times achieved by edge computing devices can give players a true online, real-time experience. The EEGTBG application has 5 modules EEG sensor, display, client, concentration calculator, and coordinator. The EEG headset senses user concentration and streams raw data to the client module. The client module filters/forwards consistent data to the concentration calculator module, which computes the concentration level of the user. The concentration level is sent to the client module, which updates the game display to the player. The coordinator module gathers and distributes measured concentration among players. The EEG sensor, display, and client modules are placed in the mobile device (e.g., smartphone). The concentration calculator and the coordinator modules can be placed in the cloudlets or at a cloud data center. The video surveillance/object tracking application (VSOT) relies on a set of distributed intelligent cameras that are able to track movement, having 6 modules (see Figure 2) : camera, motion detector, object detector, object tracker, user interface, and pan, tilt, and zoom (PTZ) control. The camera streams video to the motion detector module, which filters the incoming stream and forwards video in which motion was detected to the object detector module. The object detector module identifies the moving objects, sending object identification and position information to the object tracker, which in turn computes the desirable PTZ and sends the command to the PTZ control module. We consider that the motion detector and the PTZ control modules are always placed in the camera, while the user interface is always in the cloud. The object detector and object tracker are the two modules that should be placed by decision making policies in a cloudlet or at a cloud data center. Both applications -EEGTBG and VSOT -can be set up in a fog infrastructure to take advantage of lower latency due to the use of cloudlets. VSOT is able to work satisfactorily under data center-distance latencies (> 100 milliseconds). On the other hand, higher delays in EEGTBG can impact the players real-time perception, making the game unreal and impairing its playability. We consider that VSOT 30 and EEGTBG belong to two different classes of applications (delay-sensitive and delay-tolerant) that can benefit from a fog computing infrastructure. With the rapid use of mobile (smart) devices, fog computing infrastructure must be able to accommodate variable demands in the cloudlets, while relying on elasticity in cloud computing systems to offload processing and/or storage when necessary. This scenario is illustrated in Figure 3 , where three cloudlets are connected to a gateway that provides access to a cloud-based data center. For illustration purposes, let us assume that Cloudlet 2 is located in a city center and it supports a number of smart cameras that run the VSOT application. Let us also assume the other two cloudlets are along a path between the suburbs and the city center. During rush hours (for instance), users usually move towards the city center, and thus Cloudlet 2 will receive more load from incoming users. In our scenario, this load is characterized by EEGTBG players with their smart phones. If many EEGTBG players move to the region where Cloudlet 2 is located, it can become overloaded (processor, storage, and/or networking). Ideally, Cloudlet 2 should have enough capacity to handle the load from all its users, including the additional EEGTBG users that move towards its region. However, during many hours of the day this cloudlet would be underutilized by the VSOT application alone, which would mean low resource utilization and unnecessary energy consumption, in addition to potential operational and maintenance cost. To avoid such waste in resource use, Cloudlet 2 can be planned to support demand of applications in the lower-delay class, while also running other applications whenever feasible. Therefore, resource management policies to allocate resources between cloudlets and cloud should be able to handle variable demand whilst taking application characteristics and users mobility into account. Different application requirements along with the mobile nature of fog users calls for enhanced policies that can optimize computing resource utilization and offer quality of service accordingly. We illustrate how three different scheduling strategies can impact applications quality of service in a fognamely the Concurrent, the First Come-First Served (FCFS), and the Delay-priority strategies. The comparison is intended to show how the prioritization of low delay applications (delay-priority) would improve application execution when compared to standard resource sharing techniques (concurrent and FCFS). These algorithms should run in a cloudlet when a new application request arrives, deciding where this request should run: in the cloudlet or in the cloud. This decision can be based on both the current cloudlet load (e.g. CPU) and the request requirements (e.g. delay), as detailed below • Concurrent strategy: application requests that arrive at a cloudlet are simply allocated to such cloudlet, regardless of capacity or current usage. • First Come-First Served (FCFS) strategy: requests are served in the order of their arrival, until there are no more computing resources available. For the sake of simplicity, we only consider CPU capacity, but multi-criteria decision-making is often considered in the scheduling literature. When the cloudlet becomes full (i.e., remaining CPU capacity is smaller than application requirements), applications start to be scheduled for execution at the cloud data center. • Delay-priority: applications requiring lower-delay are scheduled first; the next class of application requests is scheduled in the cloudlet until there is no CPU capacity available, and the remaining applications are scheduled in the cloud. The strategies implement a module merging mechanism as described in the Edge-ward placement algorithm, 11 where modules of the same application are grouped to be placed at the same device. In this merging mechanism, when a module is moved to another device, all modules of the same kind are also moved to the same device.  To evaluate the different strategies in a fog computing scenario, we carried out simulations using iFogSim. The iFogSim was chosen because it runs on top of the well-established CloudSim simulator, which has been widely utilized and tested, and it is a simulator that allows the hierarchical composition of edge devices, cloudlets, and clouds, also supporting the measurement of application delays. The evaluation aims at analyzing the performance of the applications in terms of delay as well as assessing how allocation policies influence network traffic. We have set up the scenario depicted in Figure 3 with four VSOT application instances running in Cloudlet 2 and twelve EEGTBG application users in cloudlets 1 and 3. Initially, six EEGTBG users are playing the game in locations close to Cloudlet 1 and other six players are closer to Cloudlet 3. We move the EEGTBG players one by one to Cloudlet 2, emulating a mobility behavior, in order to assess any quality of service degradation resulting from poor resource allocation. Since EEGTBG has low-latency requirements, we consider that a player in a cloudlet only plays against players in the same cloudlet. Results shown focus on the analysis of Cloudlet 2, which receives applications from moving users. Each cloudlet had a processing capacity of 4,000 MIPS (millions of instructions per second) and was connected to the gateway through a link with 10,000 Kbps bandwidth and four milliseconds latency. The link between the gateway and the cloud had 10,000 Kbps bandwidth and 100 milliseconds latency. Mobile and camera devices were connected to the cloudlets through a link with 10,000 Kbps bandwidth and two milliseconds latency. The scheduling decision-making takes place before the application executes, thus the actual CPU capacity used by each application module is not precisely known at scheduling time. At scheduling time, strategies must check if a cloudlet has enough free CPU capacity to handle each application module. In the scenario we considered, each module needed, during execution, at most the CPU capacity shown in Table 1 . During execution, each application uses at a given time CPU capacity that depends on the interaction between its modules (i.e., how much data it receives from/sends to other modules, which triggers CPU-intensive actions). These estimations come from the application description, which models the application as a directed graph, or workflow, with its attributes, as commonly found in the scheduling literature. 11,12 Precise estimation, however, is a challenging issue and it is a focus of research per se. For some applications, input characteristics (e.g., video or image quality) and historical data are good indicators to estimate future performance, while other applications exhibit unpredictable behavior and estimating their future performance does not provide very accurate results. Each application has a processing loop among its modules that must be accomplished to display the results. The loop delay is the time taken for an application loop to execute. In the VSOT application this loop starts with the camera sensors producing the video stream, goes through the motion detector, object detector, object tracking, and finally PTZ control, measuring how long it takes for a object to be detected, tracked, and the camera adjusted to have better images of this object. In the EEGTBG application, the loop comprises the EEG sensor transmission to the mobile phone, the client selection of consistent readings, the concentration calculator, the client again, and the display. This measures the time taken between the sensed concentration level and the display of the current game status to the user. Figure 4 shows the delay of the VSOT and EEG-BTG application loops for the three different scheduling strategies according to the number of users that have moved from cloudlets 1 and 3 to Cloudlet 2. When only one EEGBTG player has moved to Cloudlet 2, all three strategies have the same results for both applications. When the second player moved to Cloudlet 2, different scheduling strategies start to impact the applications differently. VSOT loop is delayed with the Concurrent and Delaypriority strategies, while maintaining a low delay with the FCFS strategy. This means that scheduling using the Concurrent strategy is bringing resource  I E E E C LO U D CO M P U T I N G W W W. CO M P U T E R . O R G /C LO U D CO M P U T I N G contention to Cloudlet 2, with the VSOT application experiencing a very high delay in its control loop, resulting in quality of service degradation and consequent application misbehavior, which is avoided by FCFS by moving EEGTBG modules to the cloud. On the other hand, the Delay-priority moves VSOT modules to the cloud as a result of the higher-priority EEGTBG application arrival, thus increasing the VSOT loop delay to an acceptable level of about 200 milliseconds while maintaining the EEGTBG delays as lower as possible.
Bittencourt et al. REF studied mobility-aware application scheduling in fog computing.
Mobility-Aware Application Scheduling in Fog Computing
IEEE Cloud Computing
IEEE Cloud Computing
Computer Science