With the rapid development of the Internet of Things (IoT), emerging microservice architectures support scalable and flexible deployment to handle a significant increase in latency-sensitive requests in resource-limited edge. Due to complex data dependencies and instance sharing among microservices, service deployment and request routing tightly coupled, which motivates a complex joint optimization problem. In this case, the difficulty of service orchestration is extremely enlarged when considering multi-instance modeling and fine-grained latency analysis for the strict quality of service (QoS). Furthermore, since the objectives of end-to-end response latency and energy consumption present an inherent conflicting relationship, carefully reconciling the trade-offs between them through efficient microservice orchestration is necessary, but significantly challenging. However, most previous work failed to propose suitable approaches and models to address the above difficulties. Therefore, this paper investigates the energy-efficient microservice orchestration for latency-sensitive applications in edge computing, aiming to minimize both latency and energy consumption. We first develop a multi-instance queuing network model that accurately captures data dependencies and enables detailed analysis of queuing, computing, and communication delays. Then, we propose the Energy-efficient Determination of Microservice Instances (EDMI) algorithm to derive the minimal required number of instances. Furthermore, we design a deep reinforcement learning-based orchestration method, Global-Reward Soft Actor-Critic (GRSAC), which integrates local reward signals into global feedback to mitigate sparse rewards. Finally, we provide theoretical analysis on time complexity and convergence. Experimental results show that our proposed algorithm significantly outperforms existing approaches in reducing both response latency and energy consumption.

The big data era has accelerated the development of artificial intelligence (AI). The Model-as-a-Service (MaaS) paradigm has been used to address the substantial challenges associated with the organization and development of AI services. However, the successful delivery of complete AI applications is contingent upon the robust collaboration between microservice architectures and AI services. In this case, hybrid orchestration of AI services and microservices is highly necessary, but it still brings challenges. Furthermore, due to the heterogeneity of servers, resource competition, and multi-instance, the difficulty of hybrid orchestration modeling is enlarged. When considering intricate service dependencies among AI services and microservices, the tight coupling of deployment and routing leads to complex joint optimization problems, vastly aggravating the pressure of hybrid orchestration. Nonetheless, extant literature largely failed to address the intricate competitive and collaborative relationships between AI services and microservices, and fine-grained latency analysis with multi-instance modeling in hybrid orchestration problem. Therefore, we study joint deployment and routing for hybrid AI services and microservices in heterogeneous edge. Firstly, we conduct a precise analysis of latency and energy consumption, based on queuing networks and multi-instance models. Secondly, we propose a reinforcement learning method based on potential functions and segmented rewards (PS_SAC) to optimize end-to-end latency and system energy consumption, achieving efficient hybrid orchestration. Finally, through extensive simulation experiments, the algorithm demonstrates significant advantages in reducing latency, improving resource utilization, and lowering system energy consumption.

Service meshes built upon ubiquitous microservice architectures, as an emerging paradigm, promise to enhance the flexibility, scalability, and portability of energy-consuming and latency-sensitive applications in edge with limited resources. However, due to intricate microservice dependencies, service multiplexing, and parallel distributed instances, microservice deployment and request routing are highly interdependent. To reduce response latency and energy consumption, such collaborative optimization for efficient service mesh orchestration is necessary, but significantly challenging. Besides, strict service level objective (SLO) requirements and f ine-grained latency analysis with multi-nest routing further impose great difficulties to online orchestration. When considering multi instance modeling and multi-hop data communications for numerous microservices, the difficulty is extremely amplified. Nevertheless, most prevailing work failed to design sophisticate models and methods for addressing the above difficulties, and ignored the inherent transmission energy consumption for highly-concurrent multi-hop data interactions. Therefore, this paper investigates the energy aware service mesh deployment and online request routing in edge. First, we establish a multi-instance queuing network model to accurately analyze the end-to-end response latency with complicated dependencies and multi-hop communications, and optimize energy consumption in a fine-grained manner. Then, to boost the overall performance, we design an efficient multi-dimensional hierarchical deep reinforcement learning algorithm, which enables edges and service instances to cooperate with each other to handle massively concurrent requests. Besides, we propose an energy-aware proactive autoscaling algorithm to carefully adapt to exceedingly dynamic scenarios. Finally, extensive experiments are performed to show our superior performance compared to other baselines.

The rapid development of AI accelerates the implementation and delivery of AI applications in diverse fields. In cloud-edge collaboration, delivering a complete AI application relies on the robust coordination between AI-supporting microservices and AI services. However, most existing studies only coarsely considered monolithic AI service orchestration while neglecting microservice orchestration. Such coarse-grained orchestration severely impacts application performance. To enable diverse high-performance AI applications, fine-grained hybrid orchestration of AI services and microservices (HOAIM) is highly desirable, yet presents formidable challenges. Due to heterogeneous services, call dependencies, and service multiplexing, fine-grained hybrid orchestration modeling is highly non-trivial. Moreover, the tight coupling between deployment and routing results in a complex joint optimization problem. To address this, we first propose a heterogeneous service orchestration network that supports orchestration optimization and automated management. Then, based on queuing networks and multi-instance models, we conduct an accurate analysis of delay and load. Furthermore, to achieve efficient hybrid orchestration, we propose preference-driven resource allocation and instance computation algorithms, along with reinforcement learning with action masking and reward shaping. Finally, extensive trace-driven simulations demonstrate that our algorithms optimize average response delay by up to 41.83%, and achieve significant advantages in load balancing, response success rate, and resource efficiency.

With the rapid advancement of edge computing, service mesh has emerged as a critical technology for improving network performance, owing to its flexibility and scalability. However, massive online applications in edge clouds pose significant challenges to microservice orchestration, including high concurrency, complex service dependencies, strict response delay requirements, and fast orchestration needs. Addressing these challenges requires efficient and fast orchestration strategies, but existing approaches often lack accurate models and effective algorithms to handle these complexities. To tackle the above challenges, this paper proposes an efficient Symmetric Microservice Deployment (SMD) algorithm for fast orchestration. First, accurate modeling is achieved with the queuing network, which analyzes intertwined requests and calculates detailed delays. Moreover, the SMD algorithm simplifies the coupling between deployment and routing by considering internal dependencies during deployment. This integrated approach eliminates the need for separate routing solutions and ensures provable optimal performance under symmetric deployment. Experimental results demonstrate that, compared to four baseline algorithms, the proposed method reduces response delay by 25.5% and execution time by 58.4%, showcasing the potential and advantages of the algorithm for optimizing microservice orchestration in edge clouds networks.

The increasing processing demands of today's mobile deep learning applications impose stringent requirements on edge devices. Offloading these tasks to the cloud, while being a potential solution, often results in significant data transfer overhead, as well as privacy and connectivity concerns. To address these challenges, split machine learning (split ML) has emerged as an innovative paradigm, enabling task distribution among edge devices themselves. However, split ML systems inherently exhibit instability due to the hardware and communication limitations of mobile devices, which frequently result in failures and malfunctions of client nodes. In light of these challenges, we present Axolotl, a fault-tolerant edge split ML inference system for addressing node failure with minimal performance impact. Specifically, we first design a novel curriculum dropout mechanism to enhance the model's resilience by gradually exposing it to potential server node failures. We then design inverse-proximal weight consolidation to mitigate catastrophic forgetting caused by curriculum dropout. To further tackle potential node failures, we innovate in a resource-aware substitution module that offload the functions of a failed node to neighboring ones, ensuring efficient information flow. Extensive experiments demonstrate the effectiveness and robustness of Axolotl in various deep learning networks and tasks in edge environments.

Low Earth Orbit (LEO) satellite networks, with their low latency, high bandwidth, and global coverage, are becoming key technologies for applications like real-time video transmission. As satellite networks expand, effectively managing multicast traffic and optimizing bandwidth utilization have become major challenges for efficient video distribution. Although Software-Defined Multicast (SDM) technology has made progress in bandwidth optimization, existing SDM methods are still focused on constructing Steiner trees, making it difficult to address the dynamic changes and high-load issues in LEO satellite networks. This paper frames the multicast tree construction problem as a Joint Path Optimization Game (JPOG). We propose a Cooperative Game-Theoretic Routing (CGMR) Algorithm based on game theory, which optimizes multicast path selection and achieves load balancing by introducing a link cost-sharing mechanism. Additionally, we propose a two-stage A* path generation algorithm to improve path search efficiency. Theoretically, this paper proves that JPOG is a potential game and can converge to a pure strategy Nash equilibrium (PSNE) within a finite number of iterations. The results showed that JPOG outperformed other algorithms, achieving lower link load, path cost, and superior load balancing, demonstrating its effectiveness in optimizing multicast routing and resource management in large-scale LEO satellite networks.

The rapid development of service computing has led to the emergence of scalable and flexible architectures such as microservices and Artificial Intelligence as a Service (AaaS), enabling the orchestration of AI-driven intelligent applications. However, existing work on intelligent applications orchestration overlooked essential microservice components that support AI services, resulting in coarse-grained and incomplete models. To ensure system integrity and enhance QoS, fine-grained collaborative orchestration of microservices and AI services is crucial. However, this poses significant challenges due to complex service dependencies, high request concurrency, and heterogeneous resource demands in edge environments. Moreover, the strong coupling between service deployment and request routing complicates their joint optimization, since effective decisions in one depend on the other. To address these challenges, we propose a collaborative orchestration framework that jointly optimizes the deployment of microservices and AI services along with probabilistic request routing in edge environments. We formulate the problem as a mixed-integer nonlinear program and leverage Jackson queuing networks for accurate delay modeling. To solve this, we develop a dual time scale hybrid greedy proximal policy optimization (DTS-HGPPO) algorithm that performs instance-level deployment and adaptive routing, enhanced with iterative instance planning, action masking and intrinsic motivation mechanisms. Extensive trace-driven experiments demonstrate that our method significantly reduces both response delay and service cost compared to state-of-the-art baselines.

Microservice as a promising architecture has been widely employed in edge computing to support sensitive-latency online applications. Unfortunately, the deployment of numerous microservices creates complex invocations and requires frequent communications, which brings significant challenges to service deployment and request routing. Moreover, the strict requirements for low energy consumption and low latency in edge computing further exacerbate these difficulties. In this case, it is crucial to optimize the joint microservices deployment and request routing using a meticulous and energy-efficient approach. However, existing studies often overlook their interdependence and treat them as separate problems. Therefore, we propose a fine-grained approach in this paper to jointly optimize the deployment and request routing of microservices within edge computing scenarios. First, we utilize queuing networks to conduct detailed modeling and mathematical analysis that study the complex invocation relationships, microservice instance sharing, and communication latency. Second, we propose an energy-efficient microservice orchestration algorithm, referred to as Cluster-Processing-based Adaptive Memory Procedure. This algorithm maintains a memory storing elite solution elements, and it iteratively picks up suitable elements from the memory to construct superior solutions. Finally, extensive simulation experiments demonstrate that the proposed algorithm outperforms baseline algorithms significantly in terms of response latency and energy consumption.

Microservice architecture provides innovative solutions for delay-sensitive applications and is widely used in Mobile Edge Computing (MEC). Deploying microservices and implementing request routing within large-scale networks are confronted with numerous challenges, primarily due to intricate dependencies between microservices, frequent data communications between microservices, and the dynamic fluctuations of user request traffic. Given that the user requests are time-varying, the orchestration scheme must enable automatic scaling of microservice instances to ensure service quality. Yet, existing research mainly focuses on static microservice instance deployment, inadequately achieving the intelligent autoscaling of microservices and addressing the time-varying nature of user requests. To address these challenges in dynamic MEC networks, this paper introduces a joint optimization strategy for microservice autoscaling and routing, which adapts to the dynamic fluctuations of user request traffic. Initially, we utilize open Jackson queuing network theory to construct the model, analyzing service request queuing, communication, and processing delays along routing paths, and formulate the problem aiming to minimize deployment costs while ensuring service processing delays are not beyond the delay range that the users can accept. To address the problem, we propose a multi-stage, fine-grained dynamic scaling and routing algorithm. Extensive simulation results indicate that our approach substantially reduces network costs while maintaining network delays within a reasonable range, compared to the other state-of-the-art methods.

The rapid proliferation of Internet of Things (IoT) devices has increased the variety of devices and data traffic, making data management and analysis more complex. This complexity has raised the demand for efficient device identification methods to ensure the smooth operation of the network. Conventional identification methods rely on Machine Learning (ML) and Deep Learning (DL), which either suffer from unstable feature engineering or rely on large labeled datasets with confined representation. To overcome these shortcomings, generic hybrid representations of raw traffic are essential for precise device identification. Additionally, existing work mainly investigated device identification in clouds, incurring high network latency and computation costs. A few studies have identified IoT devices in edge, but such methods used simple neural networks, resulting in incomplete representation and redundant operations. Comprehensive representations typically require complex models, but the limited resources at the edge are insufficient to execute these models. Therefore, this paper proposes a lightweight hybrid device identification (LHDI) approach, which achieves efficient device identification in resource-constrained edge nodes. First, we adopt the unsupervised pre-training to enhance the characterization of network packets. Second, we devise LHDI by integrating bidirectional long short-term memory (Bi-LSTM) and Transformerbased blocks in a parallel configuration. Third, a pruning framework is introduced to automatically reduce Transformer parameters using structured sparsity methods without retraining. By reducing redundant neural network parameters, the proposed lightweight model facilitates effective device identification in edge, without losing representation capabilities. Experimental results demonstrate that our methods deliver high accuracy with low cost compared to others.

The integration of microservice architecture and edge computing offers innovative solutions for highly interactive, low-latency Internet applications. To manage the dynamic nature of requests in edge computing, microservice autoscaling techniques are frequently employed. However, the resource limitation of individual edge servers and the heterogeneity among edge servers present significant challenges for autoscaling in edge computing. Meanwhile, few studies have considered the long-term optimization and the joint optimization of instance adjustment and request routing in edge computing. This paper aims to fill these gaps. First, we propose Global Horizontal Pod Autoscaler (GHPA), a novel framework that addresses microservice autoscaling from the perspective of edge server clusters. Second, we consider the joint optimization of instance adjustment and request routing, and formulate a long-term optimization problem. Third, we transform the long-term optimization problem into a Markov Decision Problem (MDP) and use reinforcement learning techniques to solve it. Finally, we conduct extensive experiments using both real and synthetic data. The experiment results demonstrate that our algorithm achieves at least a 10% performance improvement in various test environments compared to state-of-the-art algorithms.

The deployment of the microservice architecture in edge networks presents new opportunities for supporting latency-sensitive network services. However, most such services are both computation-intensive and energy-consuming, posing significant challenges for edge nodes with constrained computing resources and energy supply. Therefore, designing efficient microservice orchestration strategies to reduce service latency and network energy consumption is essential but highly challenging. Due to frequent communication among microservices, service deployment and request routing are tightly coupled, which lead to a complex joint optimization problem. This complexity further increases when considering large-scale microservices under multi-instance modeling and fine-grained analysis. Nevertheless, previous work has failed to address these challenges and largely overlooked the balance between latency and energy consumption. To overcome these issues, this paper proposes an energy-latency balanced microservice orchestration method to jointly minimize service latency and energy usage. First, we adopt multi-instance modeling to enable precise end-to-end latency analysis, and integrate an energy model to quantify overall network consumption. Then, we design the Node Ranking Matrix-based Microservice Orchestration Algorithm (NRMA), which dynamically selects high-ranking nodes based on centrality and energy metrics, thereby balancing latency and energy in the deployment stage. Moreover, we use the proportional routing strategy that distributes user request traffic according to the number of deployed instances, preventing node overload and reducing cross-node communication. Experimental results show that the proposed method is significantly better than the baseline algorithms in terms of latency and energy consumption, and achieves significant results.

The emerging microservice architecture offers opportunities for accommodating delay-sensitive applications in edge. However, such applications are computation-intensive and energy-consuming, imposing great difficulties to edge servers with limited computing resources, energy supply, and cooling capabilities. To reduce delay and energy consumption in edge, efficient microservice orchestration is necessary, but significantly challenging. Due to frequent communications among multiple microservices, service deployment and request routing are tightly-coupled, which motivates a complex joint optimization problem. When considering multi-instance modeling and fine-grained orchestration for massive microservices, the difficulty is extremely enlarged. Nevertheless, previous work failed to address the above difficulties. Also, they neglected to balance delay and energy, especially lacking dynamic energy-saving abilities. Therefore, this paper minimizes energy and delay by jointly optimizing microservice deployment and request routing via multi-instance modeling, fine-grained orchestration, and dynamic adaptation. Our queuing network model enables accurate end-to-end time analysis covering queuing, computing, and communicating delays. We then propose a delay-aware reinforcement learning algorithm, which derives the static service deployment and routing decisions. Moreover, we design an energy-aware dynamic frequency scaling algorithm, which saves energy with fluctuating request patterns. Experiment results demonstrate that our approaches significantly outperform baseline algorithms in both delay and energy consumption.

The service modules of the traditional Mobile Edge Computing (MEC) are difficult to deploy, extend, and maintain in real networks because of the highly sophisticated systems. To promote the generalization, openness, and flexibility of the network edge environment, an increasing number of studies are exploring the integration of microservices with MEC. However, the existing work usually treats microservice deployment and request routing as two separate issues, ignoring the interaction between them. Therefore, this paper focuses on the joint optimization of microservice deployment and request routing in the multi-edge cloud scenarios. We establish a problem model for minimizing the average response latency, considering the transmission of requests across edge clouds. Then, in view of the complexity of the scene, this paper proposes a joint training strategy of microservice deployment and request routing based on deep reinforcement learning and Best Fit Decreasing algorithm. The algorithm takes the change of microservice deployment scheme as the action of the agent, introduces the Best Fit Decreasing algorithm to construct request routing based on the deployment scheme, and calculates rewards using the complete joint microservice deployment and request routing scheme for subsequent network training. Finally, experimental results show that the proposed algorithm can effectively reduce the response time delay and system running power compared with other algorithms.

Lightweight microservices as a software architecture have been widely adopted in online application development. However, in highly-concurrent microservice scenarios, frequent data communications, complex call dependencies, and dynamic delay requirements bring great challenges to efficient microservice orchestration. In this case, service deployment and request routing are interactively-coupled in multi-instance modeling, and cannot be locally optimized effectively, thereby enlarging the difficulty for collaborative orchestration. To accommodate time-varying request properties and dynamic microservice multiplexing, orchestration schemes are frequently adapted to real-time parallel request queues, further complicating the difficulty. Nevertheless, most previous work failed to propose appropriate models and methods for the above issues. Therefore, this paper investigates the online microservice orchestration with probabilistic routing for dynamic call graphs in clouds. First, we formulate the time-slot-based joint optimization problem as a Markov Decision Process. The open Jackson queuing networks are used to accurately establish multi-instance models and analyze the request queuing, processing, and communicating delays. Then, we propose an efficient curiosity-driven deep reinforcement learning algorithm, which meticulously implements instance-level orchestration through multi-dimensional collaborative decisions and multi-time-scale trigger events. Finally, through comprehensive trace-driven experiments, our proposed approach significantly outperforms other baselines in terms of orchestration cost and resource utilization.

Service mesh architectures are emerging as a promising microservice paradigm for developing online cloud applications. However, in large-scale microservice scenarios, frequent service communications, intricate call dependencies, and stringent latency requirements bring great pressure to efficient service mesh orchestration. In this case, the problems of service deployment and request routing based on service mesh architectures are tightly-coupled and interdependent, and cannot be effectively optimized individually, enlarging the difficulty for collaborative orchestration. When microservice multiplexing, parallel dependencies, and multi-instance modeling are considered, the difficulty is further aggravated. Nonetheless, most existing work failed to propose appropriate models and methods for the above challenges. Therefore, this article studies the large-scale service mesh orchestration with probabilistic routing and constrained bandwidths for parallel call graphs. We leverage the open Jackson queuing network theory to capture crucial microservices and analyze request processing, queuing, and communication latency for massive user requests in a fine-grained way. Then, this article proposes an efficient three-stage heuristic, which achieves elegant multi-instance consolidation and probabilistic multi-queue routing to reduce response latency and cost. We also provide the algorithm complexity and mathematical analysis of the performance. Finally, extensive trace-driven experiments are performed to validate the superiority of our proposed algorithm over other baselines.

The rapid development of satellite communication technologies has significantly enhanced global connectivity, with Low Earth Orbit (LEO) satellite networks playing a crucial role. However, the high-speed movement of LEO satellites introduces dynamic and unstable network topologies, presenting challenges in routing and traffic engineering. Traditional routing algorithms, such as Dijkstra’s, often struggle to adapt to these dynamic conditions, leading to inefficiencies in load balancing and resource utilization. In response, this paper proposes an Iterative Region-Based Probabilistic Forwarding (IRPF) strategy within a Software-Defined Satellite Networking (SDSN) framework. Our strategy dynamically assigns forwarding probabilities to satellite ports based on link traffic weights, optimizing routing paths through a feedback iteration process. To prevent the algorithm from converging to local optima, we introduce a local adjustment mechanism that fine-tunes forwarding probabilities. The experimental results show that when the scale of the satellite network is relatively small, the IRPF strategy incurs lower total link traffic costs compared to the Dijkstra algorithm. Additionally, it improves the Gini coefficient and packet loss rate by approximately 20% and 30%, respectively. These results demonstrate the effectiveness and stability of this method in routing and traffic engineering.

Pattern matching algorithms are widely used in fields such as traffic classification and management, user behavior analysis, and more. The increasingly large and complex network traffic poses significant challenges to feature matching processes. The cuckoo filter, capable of quickly determining whether an element is in a set, can be combined with pattern matching algorithms to accelerate feature matching. Building upon previous research, we propose an improved Wu-Manber (WM) algorithm that further reduces the size of the hash table generated during preprocessing, decreases the number of hash computations, and incorporates a cuckoo filter to eliminate unmatched text prefixes. This improved WM algorithm considers factors affecting algorithm performance, such as the large scale of the pattern set and the prevalence of repeated pattern string suffixes. Experimental results demonstrate that our proposed algorithm, Fast Parallel Wu-Manber (FSPRWM), significantly enhances matching speed while effectively reducing memory consumption.

Microservice architecture, as an emerging network architecture, has gained widespread adoption in latency-sensitive applications within the realm of mobile edge computing (MEC). In MEC networks, these latency-sensitive applications necessitate the concurrent processing of numerous service requests, which are composed of microservices. The complex dependencies between microservices and frequent data communication between servers contribute to the intricacy of deploying and routing microservice instances within the network. Moreover, the dynamic and unpredictable nature of service request traffic significantly complicates the timeliness and efficiency of service deployment and request routing strategies. However, existing research predominantly focuses on static network environments and neglects the time-varying characteristics of service request traffic in realistic scenarios. Consequently, we address the joint optimization problem of service deployment and request routing in the presence of dynamic service request traffic. To model the inherent data dependencies and analyze service request response latency, we employ the open Jackson queuing network. We propose a fine-grained microservice dynamic scaling (FMDS) algorithm to capture the dynamic fluctuations in service request traffic within the network. This algorithm scales microservice instances based on the principle of equal proportional change, obtaining a service deployment scheme that minimizes costs while satisfying latency constraints. Furthermore, we introduce a recursive path search algorithm that explores the service deployment scheme to determine the node forwarding probability for the entire network, adhering to the principles of fair routing. Simulation results show that the proposed method effectively improves network latency stability by 75% and enhances the timeliness of the service deployment strategy.

With the rapid growth of the on-demand economy, logistics companies and merchants increasingly struggle to meet customer demands in dynamic and uncertain conditions. This paper studies the coordinated delivery of parcels by trucks and drones under such demands, proposing a Dynamic Task Scheduling Algorithm based on Hybrid Genetic Tabu algorithm (DTSAGT) for route optimization. Simulating dynamic customer demands with a Poisson distribution and statistical methods, the algorithm addresses timeliness issues due to variations in customer needs. It optimizes drone path planning and task allocation considering drone endurance and payload limits to minimize total delivery time. The algorithm includes three steps: initial solution construction, iterative optimization, and dynamic operations. Experimental results show that DTSAGT reduces the total service time by 15.05%, 34.13%, and 35.71% on average compared to the baseline algorithms. This paper’s contribution is the combination of hybrid genetic and tabu search algorithms applied to dynamic task scheduling in truck-drone delivery, enhancing logistics efficiency.

As one of the promising self-powered sensors on Internet of Things (IoT) platforms, unmanned aerial vehicles (UAVs) have attracted much attention for parcel delivery. Their high flexibility and low cost facilitate last-one-mile delivery. However, the limitations of battery capacity and payloads prevent drones from delivering independently over large scales. In this case, it is available to employ vehicles to assist the drones. The vehicles can be private-own trucks and vehicles in public transportation systems (PTSs). Compared to trucks, PTSs, such as buses and trains, do not require extra operating and fuel costs. Given these advantages, this article adopts PTSs to assist UAVs in parcel delivery. Nevertheless, the fixed routes and schedules of public vehicles pose new challenges to the routing and scheduling problem for PTS-assisted multidrone parcel delivery (RSPMD). To tackle the problem, we propose a novel routing and scheduling algorithm, referred to as the PTS-assisted multidrone parcel delivery (PDD) algorithm. Considering the schedules of the public vehicles, the algorithm jointly optimizes the distance and time cost of drones by iteratively combining parts of existing routes. To the best of our knowledge, we are the first to address RSPMD in which UAVs ride public vehicles to deliver parcels in a wide area. Simulation results are finally presented to demonstrate that PDD outperforms existing solutions in terms of effectiveness and efficiency.

Recently, blockchain is introduced to ensure the security of the device data in Internet of Things (IoT) systems. However, storing the entire blockchain ledger in resource-constrained IoT devices is impractical. A few existing papers attempt to mitigate the storage issues of the blockchain ledgers through the collaborative storage. Nonetheless, these studies solely consider collaborative storing of the entire blockchain ledger in a single consensus unit, treating all the nodes as an individual peer but ignoring which nodes should be assigned to form a consensus unit together. This may lead to significant latency in block invocations among the nodes. To this end, this article innovatively explores the grouping of all the devices in the IoT network into multipeers at a global level which significantly reduces the access latency. In this article, we propose a clustering-based collaborative storage scheme for the blockchain in storage-limited IoT systems. The proposed algorithm takes storage and communication latency into consideration and clusters various IoT nodes into multiple peers, ensuring that the entire blockchain stays updated within these clusters. Furthermore, we propose a series of effective block allocation and replacement strategies in both the static and dynamic scenarios. The experimental results verify that our algorithm effectively solves the problem of insufficient storage in blockchain systems.

In large smart factories, massive microservices compose complicated modular IT systems, providing various service functions. However, large microservices-based IT systems incur sophisticated communications and invocations among the massive microservices, which calls for efficient orchestration techniques to meet the high requirements in smart factories. Also, complex data interdependencies among microservices tightly couple deployment with routing, further intensifying the difficulties in orchestration. Such challenges demand delicate joint optimization of service deployment and request routing, which however, are neglected by previous work. In this case, this article investigates the collaborative optimization of microservice deployment and routing in smart factories. First, we construct a communication queuing network model to analyze service performance under dynamic load. Second, two heuristics are proposed to provide differentiated deployment and routing schemes for various demands. Finally, rigorous experiments validate that our approach significantly enhances network efficiency across various production scenarios in smart factories.

The emerging low earth orbit (LEO) broadband satellite networks are creating new opportunities to enable superior video distribution. With numerous satellites deployed, broadband constellations are capable of distributing videos across the globe by efficient multicasting techniques. However, existing work only studied IP multicast for broadband constellations, which suffer from limited scalability and tree performance. With recent breakthroughs in software defined networking, novel software defined multicasting (SDM) techniques manage to achieve efficient data transfer through intelligent and granular management, outperforming traditional IP Multicast. This paper leverages software defined multicasting in the promising broadband constellations to empower satellite-based Internet video distribution. Based on rectilinear Steiner trees, this paper proposes a novel software defined multicasting framework for broadband satellite networks. In addition, this paper designs simple, agile, and scalable multicast segment routing protocols implementing source routing and equal cost multipath routing. The proposed protocols also adapt to frequent member updates and network failures with efficient tree recovery and local rerouting mechanisms. Comprehensive experiments demonstrate the effectiveness and efficiency of our approach when compared with traditional algorithms.

Edge computing technologies with container-based microservice architectures promise to provide stable and low-latency services for large-scale and complex edge applications. However, due to the limited CPU and storage resources in edge computing scenarios, the coarse-grained service deployment on edge nodes causes performance bottlenecks. In addition, the effective deployment of microservices is tightly correlated with request routing, but the current research ignores the joint optimization of multi-instance deployment and routing. In this paper, we first model the problem of jointly optimizing service deployment and routing in a dynamically changing environment with multi-edge network collaboration based on a queuing network analysis. Secondly, we design heuristic algorithms to scale microservice instances horizontally in dynamic user request states. In addition, we propose a reinforcement learning algorithm based on reward shaping (RSPPO) to minimize user waiting delay and edge network resource consumption. We also solve the microservice deployment and request routing problem for multi-edge collaboration to achieve load balancing among edge nodes. Finally, extensive experiments verify the significant and extensive effectiveness of our algorithm.

Microservices as an emerging architecture are creating new opportunities to enable superior network services in Mobile Edge Computing (MEC). In the presence of huge amounts of user requests, the massive communications among microservices have become notoriously complicated. Due to the intricate data dependencies of the microservices, the overall performance of large-scale MEC applications simultaneously depends on both service deployment and request routing. However, most existing work ignores the interdependencies of microservices and studies the deployment and routing as two isolated problems. In this case, this paper investigates the joint optimization of service deployment and request routing in edge computing. We first formulate a delay minimization problem via mixed integer linear programming and queuing analysis, and then provide a hardness proof on the problem. In addition, this paper presents a 2-approximation algorithm, followed with rigorous mathematical proofs to demonstrate the approximation ratio. The proposed two-phase algorithm consists of rounding based service deployment and adaptive-scaling-based request routing policies, which employ fine grained joint optimization to minimize service response delay. Finally, we illustrate the near-optimal performance of the proposed algorithm via comprehensive experiments.

Acoustic sensing has attracted significant attention recently, thanks to the pervasive availability of device support. However, adopting consumer-grade devices (e.g., smartphones) to deploy acoustic sensing applications faces the challenge of device/OS heterogeneity. Researchers have to pay tremendous efforts in tackling platform-dependent details even in simply accessing raw audio samples, thus losing focus on innovating sensing algorithms. To this end, this paper presents the first Acoustic Software Defined Platform (ASDP): a versatile sensing and general benchmarking platform. ASDP encompasses several customized acoustic modules running on a ubiquitous computing board, backed by a dedicated software framework. It is superior to commodity devices in controlling and reconfiguring physical layer settings, thus offering much better usability. The tailored software framework abstracts platform details and provides user-friendly interface for fast prototyping, while maintaining adequate programmability. To demonstrate the usefulness of ASDP, we showcase several relevant applications based on it. The promising outcomes make us believe that the release of our ASDP could greatly advance acoustic sensing research.

Microservices are an architectural and organizational paradigm for Internet application development. In cloud data centers, delay-sensitive applications receive massive user requests, which are fed into multiple queues and subsequently served by multiple microservice instances. Accordingly, effective deployment of multiple queues and containers can significantly reduce queuing delay, processing delay, and communication delay. Due to the increased complexity of call dependencies and probabilistic routing paths, the deployment of service instances fully interacts with request routing, bringing great difficulties to service orchestration. In this case, it is valuable to simultaneously consider service deployment and request routing in a fine-grained manner. However, most existing studies considered them as two independent components with local optimization, while data dependencies and the instance-level deployment are ignored. Therefore, this paper proposes to jointly optimize the deployment and request routing of microservice call graphs based on fine-grained queuing network analysis and container orchestration. We first formulate the problem as a mixed-integer nonlinear program and exploit open Jackson queuing networks to model intrinsic data dependencies and analyze response latency. To optimize the overall cost and latency, this paper presents an efficient two-stage heuristic algorithm, which consists of a resource-splitting-based deployment approach and a partition-mapping-based routing method. Further, this paper also provides mathematical analysis on the performance and complexity of the proposed algorithm. Finally, comprehensive trace-driven experiments demonstrate that the overall performance of our approach is better than existing microservice benchmarks. The average deployment cost is reduced by 27.4% and end-to-end response latency is reduced by 15.1% on average.

Aerial acoustic communication attracts substantial attention for its simplicity and cost-effectiveness. Unfortunately, the preferred inaudible transmission has to strike a balance between the transmission rate and communication range, when the Bit-Error-Rate (BER) is under a certain threshold. Additionally, the performance of previous proposals can be deteriorated by dynamic channel conditions including near-far problem, device heterogeneity, and multipath fading. To this end, we propose a High-speed, long-range, and Robust Chirp Spread Spectrum (HRCSS) scheme for inaudible aerial acoustic communication under dynamic channels. HRCSS innovates in the definition of a loose orthogonality condition, and it leverages this orthogonality to overlap multiple chirp carriers in a single time duration to form a data symbol representing multiple bits, thereby substantially promoting the data rate. To further enhance system robustness in long communication ranges and dynamic channel conditions, we construct a lightweight rate adaptation algorithm and design a simple yet efficient normalization method. Experiment results reveal that HRCSS achieves a significant improvement in data rate over existing methods: it delivers 500 bps data rate with a BER of 0.24 percent at 10 m, and achieves 125 bps with zero BER at 20 m. Meanwhile, HRCSS can work adaptively under dynamic channel conditions while still retaining a BER below 3 percent.

Audio-visual matching aims to learn the intrinsic correspondence between image and audio clip. Existing works mainly concentrate on learning discriminative features, while ignore the cross-modal heterogeneous issue between audio and visual modalities. To deal with this issue, we propose a novel Adversarial-Metric Learning (AML) model for audio-visual matching. AML aims to generate a modality-independent representation for each person in each modality via adversarial learning, while simultaneously learns a robust similarity measure for cross-modality matching via metric learning. By integrating the discriminative modality-independent representation and robust cross-modality metric learning into an end-to-end trainable deep network, AML can overcome the heterogeneous issue with promising performance for audio-visual matching. Experiments on the various audio-visual learning tasks, including audio-visual matching, audio-visual verification and audio-visual retrieval on benchmark dataset demonstrate the effectiveness of the proposed AML model. The implementation codes are available onhttps://github.com/MLanHu/AML.

The emerging large-scale low earth orbit (LEO) broadband satellite networks manifest great potentials in distributing videos across the globe via efficient multicast techniques. However, existing work only studied IP multicast (IPMC) for LEO constellations, which suffers from limited scalability and tree performance. In this paper, we employ the promising software defined multicast (SDM) techniques in large-scale LEO constellations to empower satellite-based Internet video distribution. We present a multi-layer rectilinear Steiner tree (ML-RST) construction algorithm for multicast routing in large-scale LEO constellations. We extend the spanning graph and edge substitution to three-dimensional (3D) scenes. Based on multi-layer spanning graphs and multi-layer edge substitution approaches, we manage to efficiently construct ML-RSTs with${O}$(${n}$log${n}$) complexity. Experimental results show that our approach can achieve an average 10% improvement in bandwidth saving compared with existing algorithms.

The emerging low earth orbit (LEO) satellite networks are expected to provide the world’s most advanced Internet services. Besides, terrestrial networks are in constant evolution and already moving to embrace the relatively new paradigm of software defined networking (SDN). In this paper, we take the advantages of SDN features and leverage traffic engineering (TE) to enhance the ISL performance in broadband LEO satellite networks. We investigate unicast and multicast TE for SDN-enhanced LEO constellations to empower satellite-based Internet services. In LEO satellite networks, unicast supports ubiquitous network access and provides basic network services, while multicast features superior satellite-based video distribution. For unicast TE in grid ISL networks, we present a simple yet efficient${k}$-segment routing based strategy with segment routing (SR) techniques, which can achieve near optimal max link utilization when compared with the multi-commodity flow solution. In the meanwhile, our solution eliminates routing tables and only imposes little routing information stored in packet headers. For multicast TE, we employ rectilinear Steiner trees (RSTs) to maximize bandwidth saving and exploit obstacle-avoiding rectilinear Steiner trees (OARSTs) to address the contention of multiple multicast groups. Based on RSTs and OARSTs, we propose an effective per-flow management scheme to balance traffic among multiple multicast flows in the presence of limited link capacities. Simulation results demonstrate the effectiveness and efficiency of our approaches on reducing routing information and accommodating more multicast groups.

Temperature is an important data source for weather forecasting, agriculture irrigation, anomaly detection, etc. While temperature measurement can be achieved via low-cost yet standalone hardware with reasonable accuracy, integrating thermal sensing into ubiquitous computing devices is highly non-trivial due to the design requirement for specific heat isolation and proper device layout. In this paper, we present the first integrated thermometer using commercial-off-the-shelf acoustic-enabled devices. Our software sonic thermometer (SST) utilizes on-board dual microphones on commodity mobile devices to estimate sound speed, which has a known relation with temperature. To precisely measure temperature via sound speed, we propose a chirp mixing approach to circumvent low sampling rates on commodity hardware and design a pipeline of signal processing blocks to handle channel distortions. SST, for the first time, empowers ubiquitous computing devices with thermal sensing capability. It is portable and cost-effective, making it competitive with current thermometers using dedicated hardware. SST is potential to facilitate many interesting applications such as large-scale distributed thermal sensing, yielding high temporal/spatial resolutions with unimaginable low costs. We implement SST on a commodity platform and results show that SST achieves a median accuracy of${0.5^\circ \mathrm{C}}$even at varying humidity levels.

Though measuring ambient temperature is often deemed as an easy job, collecting large-scale temperature readings in real-time is still a formidable task. The recent boom of network-ready (mobile) devices and the subsequent mobile crowdsourcing applications do offer an opportunity to accomplish this task, yet equipping commodity devices with ambient temperature sensing capability is highly non-trivial and hence has never been achieved. In this paper, we propose Acoustic Thermometer (AcuTe) as the first ambient temperature sensor empowered by a single commodity smartphone. AcuTe utilizes on-board dual microphones to estimate air-borne sound propagation speed, thereby deriving ambient temperature. To accurately estimate sound propagation speed, we leverage the phase of chirp signals to circumvent the low sample rate on commodity hardware. In addition, we propose to use both structure-borne and air-borne propagations to address the multipath problem. Furthermore, to prevent disruptive audible transmissions, we convert chirp signals into white noises and propose a pipeline of signal processing algorithms to denoise received samples. As a mobile, economical, highly accurate sensor, AcuTe may potentially enable many relevant applications, in particular large-scale indoor/outdoor temperature monitoring in real-time. We conduct extensive experiments on AcuTe; the results demonstrate a robust performance, a median accuracy of 0.3° C even at a varying humidity level, and the ability to conduct distributed temperature sensing in real-time.

Recently, acoustic-based indoor localization has attracted much attention due to its affordable infrastructure costs and high localization accuracy. However, previous work is infeasible in mobile target tracking for its long latency in obtaining sufficient beacon messages. In addition, the performance can further deteriorate due to device diversity, varying channel gains, and background noises. To this end, we propose an asynchronous acoustic localization and tracking system (AALTS), which utilizes distributed acoustic anchor nodes to locate passive off-the-shelf mobile devices. In AALTS, we propose an orthogonal chirp spread spectrum (OCSS) modulation technique, which doubles the data rate and thus mitigates the latency. We design a more robust method to capture acoustic signals which embody timestamps for localization, accounting for device diversity, varying channel gains, and the multipath effect. Finally, we incorporate an acoustic Doppler speed estimation module with a path-based particle filter framework to accurately track the moving targets. We have evaluated AALTS in an indoor testbed of size 8×12 m2with commodity mobile phones and customized acoustic anchors. Our evaluation results demonstrate remarkable performance: AALTS achieves 90-percentile tracking errors of 0.49 m for mobile targets and a median of 0.12 m for stationary ones with only four anchor nodes.

Indoor localization has witnessed a rapid development in the past few decades. Tremendous solutions have been put forwarded in the literature and the localization accuracy has reach an unprecedent centimeter-level. Among the available approaches, acoustic-enabled solutions have attracted much attention. They customarily achieve decimeter-level localization accuracy with affordable infrastructure costs. However, there still exist several open issues for the acoustic-based approaches which prohibit their wide-scale adoptions. First, although extra infrastructures (i.e., beacons) are economical, deployment, and maintenance can incur excessive labor cost. Second, current approaches have much latency to obtain a location fix, making it infeasible for mobile target tracking. Third, the localization performance of current solutions degrades easily by the near-far problem, multipath effect, and device diversity. To address these issues, this paper presents an asynchronous acoustic-based localization system with participatory sensing. We leverage the collaborative efforts of the participatory users who are relatively stationary in indoor environments as virtual anchors (VAs) to eliminate the predeployment and post-maintenance costs incurred in traditional anchor-based solutions. To mitigate the latency to obtain a location fix, we design an orthogonal ranging mechanism to enable concurrent beacon message transmission, which is $2\boldsymbol \times $ faster than previous work in obtaining a location fix. Moreover, we propose a robust method to address the near-far problem and device diversity, and we conquer the multipath problem via a genetic algorithm-based approach. Our VA-based system is self-deployable, cost-effective, and robust to environmental dynamics. We have implemented and evaluated a system prototype, demonstrating a median accuracy of 0.98 m in typical indoor settings.

The enabling Internet-of-Things technology has inspired many innovative sensing mechanisms by repurposing the onboard sensors. Leveraging the built-in acoustic sensors for ranging is among one of the interesting applications. However, among the few studies on acoustic ranging, the one-way sensing method suffers from synchronization errors and requires cumbersome kernel modifications; the other two-way approaches overcome these shortcomings, but they are sensitive to system delays. In this case, this paper proposes a novel lightweight one-way sensing paradigm without the above drawbacks. The key insight of this paper is to perform ranging by estimating the propagation time of acoustic signals via linear frequency modulation signal mixing. Such a signal mix operation can translate range estimation into fine-grain frequency estimation, thereby enhancing ranging accuracy. In addition, our system can have multiple receivers co-exist and thus the measurement dimensions are boosted. We have implemented and evaluated our system prototype in real-world settings. The prototype demonstrated centimeter-level ranging performance.

In recent decades, unmanned aerial vehicles (UAVs, also known as drones) equipped with multiple sensors have been widely utilized in various applications. Nevertheless, constrained by limited battery capacities, the hovering time of UAVs is quite limited, prohibiting them from serving a wide area. To cater with remote sensing applications, people often employ vehicles to transport, launch, and recycle them. The so-called vehicle-drone cooperation (VDC) benefits from both the far driving distance of vehicles and the high mobility of UAVs. Efficient routing and scheduling can greatly reduce time consumption and financial expenses incurred in VDC. However, previous works in vehicle-drone cooperative sensing considered only one drone, thus unable to simultaneously cover multiple targets distributed in an area. Using multiple drones to sense different targets in parallel can significantly promote efficiency and expand service areas. Therefore, we propose a novel problem, referred to as vehicle-assisted multidrone routing and scheduling problem. To tackle the problem, we contribute an efficient algorithm, referred to as vehicle-assisted multi-UAV routing and scheduling algorithm (VURA). In VURA, we maintain and iteratively update a memory containing candidate UAV routes. VURA works by iteratively deriving solutions based on UAV routes picked from the memory. In every iteration, VURA jointly optimizes anchor point selection, path planning, and tour assignment via nested optimization operations. To the best of our knowledge, we are the first to tackle this novel yet challenging problem. Finally, performance evaluation is presented to demonstrate the effectiveness and efficiency of our algorithm when compared with existing solutions.

The enabling Internet-of-Things (IoT) technology has inspired a large number of novel platforms and applications. One popular IoT platform is unmanned aerial vehicles (UAVs, also known as drone). Benefiting from the intrinsic flexibility, convenience, and low cost, UAVs have great potentials to be utilized in various civil applications, including parcel delivery. However, suffering from limited payloads and battery capacities, it is uneconomical for UAVs to perform parcel delivery tasks independently. To conquer the drawbacks of low payloads and battery capacities, people propose to employ both trucks and drones to construct truck-drone parcel delivery systems. However, previous works only leverage either independent drones or truck-carried drones to collaborate with trucks. In contrast, in this article we propose to simultaneously employ trucks, truck-carried drones, and independent drones to construct a more efficient truck-drone parcel delivery system. We claim that such a hybrid parcel delivery system can fully exploit the complementary benefits of the three platforms. We propose a novel routing and scheduling algorithm, referred to as hybrid truck-drone delivery (HTDD) algorithm, to solve the hybrid parcel delivery problem, wherein M drones carried by M trucks, together with N independent drones, cooperate to deliver parcels to customers distributed in a wide region. The experimental results show that our algorithm outperforms the existing solutions which employ either independent drones or truck-carried drones.

Energy-saving (ES) systems developed on the basis of the Internet-of-Things (IoT) by heavily relying on automated understanding of human behaviors and activities recognition is of paramount importance in smart home. However, classic approaches are incapable to understand the relations among users' contexts and ES of appliances very well, and they cannot handle massive metering and time-varying user context datasets. Moreover, privacy concern is thoroughly aroused from both the residential and utility provider sides as to its essentiality. To tackle these problems, we propose a privacy-preserving and residential context-aware online ES (PRCOES) system in an IoT-enabled smart home environment. We model the repeated interaction of ES of appliances and the activity recognition of user context as a contextual multiarmed bandits (CMAB) problem, where the context-aware online learning algorithm can predict appropriate energy offers (EOs) that could meet the users' satisfaction, task completion rate, and ES purposes for appliances. We utilize a tree-based structure expanding from top to bottom to recommend EOs, which supports ever-increasing big metering datasets with user context-awareness. Theoretical analysis shows that our proposal achieves sublinear regret and differential privacy for both residents and utility provider. Experiments results validate that PRCOES could enhance users' experience and prolong users' engagement in everyday ES while guarantee the privacy for both residents and utility provider.

This paper studies a scheduling problem of task graphs on a nondedicated networked computing platform. The networked platform is characterized by a set of fully connected processors such as a multiprocessor system that can be shared by multiple tasks. Therefore, the computation and communication capacities of the computing platform dynamically fluctuate. To deal with this fluctuations for high performance task graph computing, we propose an online dynamic resilience scheduling algorithm called Adaptive Scheduling Algorithm (ASA) that bears certain distinct features compared to existing algorithms. First, the proposed algorithm deliberately assigns tasks to idle processors in multiple rounds to prevent any unfavorable decisions and also to avoid inefficient assignments of certain key tasks to slow processors. Second, the algorithm adopts task duplication as an attempt to minimize serious increase of schedule length due to unexpected processor slowdown. Finally, a look-ahead message transmission policy is applied to save communication time and further improve the overall performance. Performance evaluation results are presented to demonstrate the effectiveness and competitiveness of our approaches when compared with the existing algorithms.

Mobile crowdsensing leverages mobile devices (e.g., smart phones) and human mobility for pervasive information exploration and collection; it has been deemed as a promising paradigm that will revolutionize various research and application domains. Unfortunately, the practicality of mobile crowdsensing can be crippled due to the lack of incentive mechanisms that stimulate human participation. In this paper, we study incentive mechanisms for a novel Mobile Crowdsensing Scheduling (MCS) problem, where a mobile crowdsensing application owner announces a set of sensing tasks, then human users (carrying mobile devices) compete for the tasks based on their respective sensing costs and available time periods, and finally the owner schedules as well as pays the users to maximize its own sensing revenue under a certain budget. We prove that the MCS problem is NP-hard and propose polynomial-time approximation mechanisms for it. We also show that our approximation mechanisms (including both offline and online versions) achieve desirable game-theoretic properties, namely truthfulness and individual rationality, as well as O(1) performance ratios. Finally, we conduct extensive simulations to demonstrate the correctness and effectiveness of our approach.

High-performance computing (HPC) systems, including Clusters, Grids and the most recent Clouds, have emerged as attractive platforms to tackle various applications. One significant type of applications in the HPC systems is workflow computation, which has been applied in various scientific and engineering domains. The workflow computation frequently produces intermediate result files, which become garbage after being used and are usually cleaned up without making any contribution to future computation. In this paper, we argue that such garbage data could be useful in the future computation and should not be immediately cleaned up. This is because workflow computation usually contains multiple instances that may share some common data products produced in the past. This sharing scheme provides opportunities to reuse the historical data to speed-up subsequent computation and simplify re-computation due to faulty or crashed runs. To this end, we propose a novel approach, referred to as garbage data manager (GDM), for the workflow computation in HPC systems. The GDM organizes and manages the garbage data for batch schedulers to enhance the performance of subsequent computation. The essence of the GDM is to record the history of computation by constructing a dataflow graph on per instance (run) basis and set up inheritance relationships between the different instances of the same workflow, called run-tree, to achieve the data reuse. Our simulation results demonstrate that exploiting the garbage data is an effective way of improving the workflow computation.

In this paper, we study the problem of co-migrating a set of service replicas residing on one or more redundant virtual servers in clouds in order to satisfy a sequence of mobile batch-request demands in a cost effective way. With such a migration, we can not only reduce the service access latency for end users but also minimize the network costs for service providers. The co-migration can be achieved at the cost of bulk-data transfer and increases the overall monetary costs for the service providers. To gain the benefits of service migration while minimizing the overall costs, we propose a co-migration algorithmMigkfor multiple servers, each hosting a service replicas.Migkis a randomized algorithm with a competitive cost of$O(\frac{\gamma\, \log \,n}{\min \lbrace \frac{1}{\kappa },\frac{\mu }{\lambda \,+\,\mu }\rbrace })$to migrate$\kappa$services in a static$n$-node network where$\gamma$is the maximal ratio of the migration costs between any pair of neighbor nodes in the network, and where$\lambda$and$\mu$represent the maximum wired transmission cost and the wireless link cost respectively. For comparison, we also study this problem in its static off-line form by proposing a parallel dynamic programming (hereafter DP) based algorithm that integrates the branch&bound strategy with sampling techniques in order to approximate the optimal DP results. We validate the advantage of the proposed algorithms via extensive simulation studies using various requests patterns and cloud network topologies. Our simulation results show that the proposed algorithms can effectively adapt to mobile access patterns to satisfy the service request sequences in a cost-effective way.

The scheduling of tasks with deadlines on clusters is a key issue for offering quality-of-service (QoS) assurance. A critical challenge in real-time task scheduling is to handle various types of applications. This paper investigates the scheduling problem for processing a set of tasks comprising both divisible and indivisible real-time tasks on cluster systems. Indivisible tasks are characterized by the property that they need to be processed on their entirety on a single processor while divisible tasks can be distributed across several processing nodes by exploiting the underlying data parallelism. We propose a dynamic (on-line) real-time scheduling algorithm referred to as Hybrid Loads Push-Pull Scheduling (HLPPS) algorithm for handling a set of tasks comprising both divisible and indivisible real-time tasks on cluster systems. HLPPS is shown to efficiently exploit the parallelism in divisible tasks without undermining the schedulability of indivisible tasks and thereby optimize the overall performance. We consider two distinct network platforms - tightly coupled and loosely coupled clusters in designing the strategy. We conduct extensive performance evaluation studies to quantify the performance of the proposed algorithm under a variety of scenarios.

As time-triggered communication protocols [e.g., time-triggered controller area network (TTCAN), time-triggered protocol (TTP), and FlexRay] are widely used on vehicles, the scheduling of tasks and messages on in-vehicle networks becomes a critical issue for offering quality-of-service (QoS) guarantees to time-critical applications on vehicles. This paper studies a holistic scheduling problem for handling real-time applications in time-triggered in-vehicle networks where practical aspects in system design and integration are captured. The contributions of this paper are multifold. First, it designs a novel scheduling algorithm, referred to asUnfixed Start Time(UST) algorithm, which schedules tasks and messages in a flexible way to enhance schedulability. In addition, to tolerate assignment conflicts and further improve schedulability, it proposes two rescheduling and backtracking methods, namely,Rescheduling with Offset Modification(ROM) andBacktracking and Priority Promotion(BPP) procedures. Extensive performance evaluation studies are conducted to quantify the performance of the proposed algorithm under a variety of scenarios.

Content distribution networks (CDNs) built on clouds have recently started to emerge. Compared to conventional CDNs, cloud-based CDNs have the benefit of cost efficient hosting services without owning infrastructure. However, resource provisioning and replica placement in cloud CDNs involve a number of challenging issues, mainly due to the dynamic nature of demand patterns. To deal with this dynamic nature, this paper proposes a set of novel algorithms to solve the joint problem of resource provisioning and caching (i.e., replica placement) for cloud-based CDNs with an emphasis on handling the dynamic demand patterns. Firstly, we propose a provisioning and caching algorithm framework called Differential Provisioning and Caching (DPC) algorithm, which aims to rent cloud resources to build CDNs and whereby to cache contents so that the total rental cost can be minimized while all demands are served. DPC consists of 2 steps. Step 1 first maximizes total demands supported by unexpired resources. Then, step 2 minimizes the total rental cost for new resources to serve all remaining demands. For each step we design both greedy and iterative heuristics, each with different advantages over the existing approaches. Moreover, to dynamically adjusts the placement of contents and route maps, we further propose the Caching and Request Balancing (CRB) algorithm, which is light-weight and thus can be frequently executed as a companion of DPC to maximize the total demands. Performance evaluation results are presented to demonstrate the effectiveness and competitiveness of our approaches when compared to existing algorithms.

Grids have been extensively deployed to handle various scientific and engineering applications that can be structured as bag-of-tasks (BoT). The scheduling of BoT applications on Grids is an important issue for achieving high performance. Grid scheduling involves a number of challenging issues, mainly due to the dynamic nature of the Grid. To deal with this dynamic nature, in this paper, we propose an online scheduling algorithm called prudent algorithm with replication (PAR) for scheduling Grid applications. PAR is shown to prudently make scheduling decisions in such a way that it can tolerate inaccurate performance predictions. Another point to note is that PAR adopts task duplication as an attempt to reduce serious schedule increases. Moreover, since the applications to be performed may widely vary in terms of their required hardware and software, we also capture the loads' various processing requirements in our algorithms, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus, in our problem formulation each application can only be processed by certain processors as both the applications and processing nodes are heterogeneous. We then present a task selection policy, referred to as requirement-aware load selection (RALS) policy to handle the contention of multiple applications that have various processing requirements but share the same computing resources. Based on RALS and PAR, we develop two scheduling algorithms: requirement-aware prudent algorithm with replication (RAPAR), and requirement-aware knowledge-free algorithm with replication (RAKAR). RAPAR and RAKAR address the scheduling of multiple BoT applications with heterogeneous processing requirements on Grids. RAPAR works in scenarios where inaccurate performance prediction information is provided whereas RAKAR works without any prediction information. Performance evaluation results are presented to demonstrate the effectiveness and competitiveness of our approaches when compared to existing algorithms.

This paper investigates the problem of scheduling multiple divisible loads in networked computer systems with a particular emphasis in capturing two important real-life constraints, the arbitrary processor release times (or ready times) and heterogeneous processing requirements of different loads. We study two distinct cases of interest, static case, where processors' release times are predetermined and known, and dynamic case, where release times are unknown until processors are released. To address the two cases, we propose two novel scheduling strategies, referred to as Static Scheduling Strategy (SSS) and Dynamic Scheduling Strategy (DSS), respectively. In addition, we capture a task's processing requirements in our strategies, a unique feature that is applicable for handling loads on networks that run proprietary applications only on certain nodes. Thus, each task can only be processed by some certain nodes in our formulation. To handle the contention of multiple applications that have various processing requirements but share the same processing nodes, we propose an efficient load selection policy, referred to as Most Remaining Load First (MRF). We integrate MRF into SSS and DSS to address the problem of scheduling multiple divisible loads with arbitrary processor release times and heterogeneous requirements. We evaluate the strategies using extensive simulation experiments.