PaperlayerView exact revision on arXiv

Source-linked AI summary

A Cooperative Scheduling Scheme of Local Cloud and Internet Cloud for Delay-Aware Mobile Cloud Computing

Tianchu Zhao, Sheng Zhou, Xueying Guo, Yun Zhao, Zhisheng Niu

arXiv:1511.08540v1cs.NIcs.DC

TL;DR

Mobile cloud computing can save device energy, but remote Internet transmission challenges delay requirements and local-cloud compute is limited. The paper proposes threshold-based cooperation with delay-aware priorities; cooperation improves success probability, and the optimal thresholds vary with traffic load.

  • Problem

    Remote execution can challenge application delay requirements, while local-cloud resources are limited and average delay does not assess whether individual application bounds are met.

    Source: §I · p. 1

  • Method

    A threshold-based policy cooperatively schedules local and Internet clouds, prioritizing tasks by delay requirement and tuning thresholds to maximize successful completion within deadlines.

    Source: §I · p. 2, D. Optimization Objective · p. 3, §III · p. 3

  • Results

    More than 20% success probability of tasks can be enhanced by cooperation between the local cloud and Internet cloud.

    Source: §IV · p. 5

  • Takeaways & Limitations

    Optimal buffer thresholds depend on traffic load: B2 rises as arrivals increase, then falls under heavy load, while B1 decreases as arrivals increase.

    Source: §IV · p. 6

Abstract

from arXiv · show

With the proliferation of mobile applications, Mobile Cloud Computing (MCC) has been proposed to help mobile devices save energy and improve computation performance. To further improve the quality of service (QoS) of MCC, cloud servers can be deployed locally so that the latency is decreased. However, the computational resource of the local cloud is generally limited. In this paper, we design a threshold-based policy to improve the QoS of MCC by cooperation of the local cloud and Internet cloud resources, which takes the advantages of low latency of the local cloud and abundant computational resources of the Internet cloud simultaneously. This policy also applies a priority queue in terms of delay requirements of applications. The optimal thresholds depending on the traffic load is obtained via a proposed algorithm. Numerical results show that the QoS can be greatly enhanced with the assistance of Internet cloud when the local cloud is overloaded. Better QoS is achieved if the local cloud order tasks according to their delay requirements, where delay-sensitive applications are executed ahead of delay-tolerant applications. Moreover, the optimal thresholds of the policy have a sound impact on the QoS of the system.

I. INTRODUCTION

Mobile cloud computing can save device energy, but remote execution challenges application latency requirements while local clouds have limited compute. The paper proposes cooperative scheduling across local and Internet clouds, with delay-aware priorities and a system that routes tasks through a local scheduler.

I. INTRODUCTION

  • Remote execution can save smartphone energy, but Internet transmission delay can make centralized-cloud execution miss application delay requirements.The introduction cites MAUI and CloneCloud as MCC platforms.Source: §I · p. 1
  • Local clouds reduce transmission delay but have limited compute; cooperating cloudlets can still face high-load constraints, and average delay does not capture application-specific bounds.The paper also notes that cloud resources should be deployed in balance with cost and QoS because resources beyond a threshold provide only marginal gain.Source: §I · p. 1
  • The proposed policy offloads delay-tolerant tasks to the Internet cloud above a load threshold and gives delay-sensitive tasks higher local-cloud priority.The design combines the local cloud's proximity with the Internet cloud's abundant compute resources.Source: §I · p. 2

II. SYSTEM MODEL AND PROBLEM FORMULATION

  • Mobile applications are modeled as arriving tasks with delay constraints, and resource allocation aims to maximize the probability of completing them within those constraints.Users send tasks to a local-cloud scheduler, which chooses local execution or Internet-cloud execution before returning results.Source: §II · p. 2

A. Tasks

The model groups arrivals by delay requirement and represents local execution as a finite-buffer priority queue. Tasks with shorter deadlines receive higher priority, but running tasks are not interrupted.

A. Tasks

  • The model assumes N task types with Poisson arrival rates λ_i, exponential service rate μ, and system delay constraints T_i equal to each requirement minus τ.Tasks are ranked by their delay requirements.Source: A. Tasks · p. 2

B. Local Cloud

  • The local cloud is modeled as C servers with finite per-type buffers and a nonpreemptive priority queue, where shorter-deadline tasks have higher priority.Total delay comprises queueing and execution delay.Source: B. Local Cloud · p. 2

C. Internet Cloud

Internet-cloud execution has long transmission delay and jitter, so it is not generally suited to delay-constrained tasks. The model uses it when local service capacity is exceeded and neglects its execution delay relative to transmission delay.

C. Internet Cloud

  • The Internet cloud is used when arrivals exceed local service capacity, with its execution delay treated as negligible compared with transmission delay.The model characterizes Internet transmission as having long mean delay and jitter.Source: C. Internet Cloud · p. 2
  • We adopt reference ’s model for Internet transmission delay: ϕ1(t) is the router-delay distribution, and ϕ2(t) is the queuing-delay distribution.Source: C. Internet Cloud · pp. 2–3

D. Optimization Objective

The optimization objective is to maximize the probability that an arriving task completes within its delay constraint, subject to the local cloud's server limit.

D. Optimization Objective

  • The objective is maximizing P_success(t < T_i | C), the probability an arriving task completes within its delay constraint given at most C local-cloud servers.The policy chooses when and where to execute arriving tasks.Source: D. Optimization Objective · p. 3

III. POLICY DESIGNMENT AND PERFORMANCE OPTIMIZATION

The policy uses priority-specific buffer thresholds to decide when tasks are sent from the local cloud to the Internet cloud. Its design balances delay requirements against queue length, and the paper compares it with several alternative scheduling policies.

III. POLICY DESIGNMENT AND PERFORMANCE OPTIMIZATION

  • Priority-specific thresholds send an arriving task to the Internet cloud when the relevant buffer is full; otherwise, queued tasks are served in priority order.Tasks start in the local cloud when a server is empty, and a freed server takes the highest-priority waiting task.Source: §III · p. 3
  • Thresholds are intended to improve success probability by limiting queue lengths, while preventing higher-priority arrivals from undermining a queued task's prospects.The policy does not admit a higher-priority task when a lower-priority task is last in a queue already at its threshold.Source: §III · p. 3
  • The comparisons include local-cloud-only, greedy, FCFS-based cooperation, and non-buffer policies.The FCFS-based policy compares current queue length with a threshold; the non-buffer policy offloads arrivals whenever all local servers are busy.Source: §III · p. 3

A. Stationary Distribution

The queuing system is represented as an N-dimensional Markov chain, whose stationary distribution is obtained from global balance equations. The paper establishes that this distribution is unique and describes the states and buffer boundaries in the two-priority case.

A. Stationary Distribution

  • The N-dimensional Markov chain's stationary distribution is obtained by formulating and solving the global balance equations.The paper states that the chain has only one stationary distribution because all states communicate and it is irreducible.Source: A. Stationary Distribution · p. 3
  • In the two-priority chain, states below the dashed line represent busy-server counts with an empty queue, while states above it represent queue lengths when all servers are busy.States at either buffer boundary indicate that the buffer is full and arrivals are offloaded to the Internet cloud.Source: A. Stationary Distribution · p. 3, Figure 4 · p. 4

B. Sojourn Time Distribution

The sojourn-time model distinguishes tasks served immediately by the local cloud from those that must wait, and treats Internet-cloud sojourn time separately. For queued local tasks, it builds the sojourn-time distribution from waiting and service time.

B. Sojourn Time Distribution

  • When s≤C, a task is served immediately and its sojourn time is its exponentially distributed service time; when s>C, it waits for local service or is served by the Internet cloud.For local service in the latter case, sojourn time comprises waiting time and service time.Source: B. Sojourn Time Distribution · p. 4
  • For a priority-i task that waits locally, the waiting-time distribution is an (Li+1)-fold convolution of the busy-period distribution for higher-priority tasks, and sojourn time convolves waiting with service.The busy period is for a C-server system serving higher-than-i priority tasks.Source: B. Sojourn Time Distribution · p. 4
  • Internet-cloud sojourn time is modeled with the empirical distribution PI(t).Source: B. Sojourn Time Distribution · p. 4

C. Success Probability

The section calculates success probability for each task priority and combines those probabilities into a total success probability. The priority-specific calculation depends on the arrival rates, service rate, and buffer thresholds.

C. Success Probability

D. Local Optimal Thresholds

A recursive procedure finds local-optimal buffer thresholds by incrementally increasing each threshold while success probability does not decrease. In the simulations, its thresholds match those from global search.

D. Local Optimal Thresholds

  • The algorithm initializes all thresholds at zero and increments them in sequence, stopping each increase when success probability begins to decrease.It first optimizes B_N, then optimizes preceding thresholds while recalculating the thresholds that follow them.Source: D. Local Optimal Thresholds · p. 4
  • The recursive procedure gives local-optimal thresholds, whereas search finds the global optimum.Source: D. Local Optimal Thresholds · p. 4
  • In the simulation scenarios, the recursive algorithm's thresholds equal those derived by search.Source: D. Local Optimal Thresholds · p. 4

IV. NUMERICAL RESULTS

The numerical results compare cooperation policies with local-cloud and non-priority alternatives across traffic loads. Cooperation and priority ordering improve success probability, while optimal buffer thresholds vary with arrival rate.

IV. NUMERICAL RESULTS

  • The evaluation models delay-sensitive and delay-tolerant tasks with delay requirements of 50 and 300 milliseconds, respectively.Internet delay has a 200-millisecond mean, and the local-cloud server has a 10-millisecond mean service time.Source: §IV · pp. 4–5
  • More than 20% success probability is enhanced by local-cloud and Internet-cloud cooperation under heavy traffic.The comparison is between the priority-based cooperation policy and the local-cloud policy.Source: Figure 5 · p. 5, §IV · p. 5
  • Considering task priorities improves success probability by 5% over FCFS cooperation in the model.The priority policy executes delay-sensitive tasks ahead of delay-tolerant tasks.Source: §IV · p. 5, Figure 6 · p. 5
  • Threshold B1 decreases as arrival rate increases, reducing waiting time for all task types.Source: §IV · p. 6
  • Optimal buffer threshold B2 rises with arrival rate, then should decrease under heavy traffic to limit waiting time.At low traffic, a small B2 is optimal; at heavy traffic, a full queue makes long waiting times likely.Source: Figure 7 · p. 6, §IV · p. 6

V. CONCLUSION

The conclusion reports improved QoS from cooperative local- and Internet-cloud scheduling, priority ordering, and traffic-dependent threshold optimization.

V. CONCLUSION

  • The proposed scheduling scheme coordinates local and Internet cloud resources to improve MCC users' QoS.Source: §V · p. 6
  • Cooperation improves task success probability by 20%, and priority scheduling adds a 5% improvement in the model.The priority scheme executes delay-sensitive tasks ahead of delay-tolerant tasks.Source: §V · p. 6
  • Optimal buffer thresholds depend on traffic load: they grow to hold more tasks, then decrease under heavy load to limit waiting time.Source: §V · p. 6
Loading 1511.08540v1…