检索结果-内蒙古大学图书馆

GT-scheduler: a hybrid graph-partitioning and tabu-search based task scheduler for distributed data stream processing systems

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2024年第5期27卷 5815-5832页

作者： Hadian, Hamid Sharifi, Mohsen Virginia Tech Dept Elect & Comp Engn ECE Blacksburg VA 24061 USA Iran Univ Sci & Technol Sch Comp Engn Tehran Iran

The continual increase in the amount of generated data by social media, IoT devices, and monitoring systems have motivated the use of distributed data stream processing (DSP) systems to harness data in a real-time manner. The scheduling of processing tasks in DSP systems across the machines in a cluster or cloud environment is an NP-Hard problem. Different scheduling schemes have been proposed to address the scheduling problem, but most fail to take into account the runtime adaptation and workload changes after initial scheduling. In this paper, we propose a new scheduler (GT-Scheduler) that leverages a heuristic and rule-based algorithm to schedule tasks at near-optimal performance alongside using a meta-heuristic algorithm to make runtime adaptation. Firstly, K-way graph partitioning divides the tasks in an application graph according to the communication patterns. It places tasks with the highest amount of communication near each other to limit an increase in the topology response time. Secondly, instead of assigning tasks to the worker nodes, a partition of tasks is assigned to the nodes by adopting a greedy strategy. If the capacity of nodes is insufficient to host a specific partition of tasks, this partition is iteratively divided by the k-partitioning algorithm to assign to a proper node. The idea of runtime adaptation lies in detecting overutilized worker nodes and reassigning their tasks by exploiting a Tabu-Search and a new scoring strategy to find the best solution in a way that no worker node is overutilized. GT-Scheduler is implemented on the standard Apache Storm and using the standard benchmarks, it is shown that GT-Scheduler outperforms the R-Storm and the Online-Scheduler by at least 35% in reducing the topology response time.

关键词： distributed data stream processing Scheduling Graph partitioning Tabu search Apache storm Heterogeneous cluster

来源：评论

学校读者我要写书评

暂无评论

An elastic and traffic-aware scheduler for distributed data stream processing in heterogeneous clusters

引用

JOURNAL OF SUPERCOMPUTING 2023年第1期79卷 461-498页

作者： Hadian, Hamid Farrokh, Mohammadreza Sharifi, Mohsen Jafari, Ali Univ Sci & Technol Sch Comp Engn Distributed Syst Res Lab Tehran Iran

Existing data stream processing (DSP) systems perform poorly while encountering heavy workloads, particularly on clustered set of (heterogeneous) computers. Elasticity and changing application parallelism degree can limit the performance degradation in the face of varying workloads that negatively impact the overall application response time. Elasticity can be achieved by operator scaling, i.e., by replication and relocation in operators at runtime. However, scaling decisions at runtime is challenging, since it first increases the overall communication overhead between operators and secondly changes any initial scheduling that could lead to a non-optimal scheduling plan. In this paper, we investigate the problem of elasticity and scaling decisions and propose a DSP system called ER-Storm. To curb communication overhead, we propose a new 3-step mechanism for replication and relocation of operators upon detecting a bottleneck operator that overutilizes a worker node. The other challenge is to select the proper worker nodes to host relocated operators. By discretizing the input workload, we model the relocation of operators between worker nodes at runtime through a scalable Markov Decision Process (MDP) and use a model-free notion of reinforcement learning (Q-Learning) to find optimal solutions. We have implemented our propositions on the Apache Storm version 2.1.0. Our experimental results show that ER-Storm reduces the average topology response time by 20-60 percent based on the rate of input workload (low or high) compared to the R-Storm scheduler and the Online-Scheduler of Storm.

关键词： distributed data stream processing Elasticity Scheduling Resource-awareness Heterogeneous clusters Reinforcement learning Apache storm

来源：评论

学校读者我要写书评

暂无评论

Efficient Operator Placement for distributed data stream processing Applications

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2019年第8期30卷 1753-1767页

作者： Nardelli, Matteo Cardellini, Valeria Grassi, Vincenzo Lo Presti, Francesco Univ Roma Tor Vergata I-00133 Rome Italy

In the last few years, a large number of real-time analytics applications rely on the data stream processing (DSP) so to extract, in a timely manner, valuable information from distributed sources. Moreover, to efficiently handle the increasing amount of data, recent trends exploit the emerging presence of edge/Fog computing resources so to decentralize the execution of DSP applications. Since determining the Optimal DSP Placement (for short, ODP) is an NP-hard problem, we need efficient heuristics that can identify a good application placement on the computing infrastructure in a feasible amount of time, even for large problem instances. In this paper, we present several DSP placement heuristics that consider the heterogeneity of computing and network resources;we divide them in two main groups: model-based and model-free. The former employ different strategies for efficiently solving the ODP model. The latter implement, for the problem at hand, some of the well-known meta-heuristics, namely greedy first-fit, local search, and tabu search. By leveraging on ODP, we conduct a thorough experimental evaluation, aimed to assess the heuristics' efficiency and efficacy under different configurations of infrastructure size, application topology, and optimization objectives.

关键词： distributed data stream processing geo-distributed systems heuristics operator placement quality of service

来源：评论

学校读者我要写书评

暂无评论

Model verification of real-time and distributed stream processing architecture

引用

COMPUTING 2025年第1期107卷 1-25页

作者： Ganji, Binazir Rezaee, Ali Adabi, Sahar Movaghar, Ali Islamic Azad Univ Dept Comp Engn Sci & Res Branch Tehran Iran Islamic Azad Univ Dept Comp Engn North Tehran Branch Tehran Iran Sharif Univ Technol Dept Comp Engn Tehran Iran

Real-time data processing systems are required to manage large volumes of data and deliver instant feedback. These systems are typically constructed on distributed processing architectures, where addressing the challenges of preventing deadlocks, avoiding divergence, ensuring liveness, and achieving goal reachability is highly complex before the architecture is implemented. This paper presents a framework for verifying formal models of a distributed and real-time stream processing architecture. It can be used to analyze the concurrent behavior of processes in stream data processing architectures. For the case study, a social network stream processing system was modeled. In the proposed method, Communicating Sequential Processes (CSP) and the Process Analysis Toolkit (PAT) were used to properties verification such as deadlock-free, divergence-free, liveness, and goal reachability before architecture implementation. The results indicate that our approach for real-time and distributed processing architecture, enables early detection of design errors in the initial stages, reduces costs, ensures real-time system constraints, identifies performance bottlenecks, and examines the behavior of concurrent system processes under various conditions.

关键词： Real-time stream processing distributed data stream processing Kappa architecture Model verification CSP

来源：评论

学校读者我要写书评

暂无评论

data-Trace Types for distributed stream processing Systems 2019

Data-Trace Types for Distributed Stream Processing Systems

引用

40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) part of ACM's Federated Computing Research Conference (FCRC)

作者： Mamouras, Konstantinos Stanford, Caleb Alur, Rajeev Ives, Zachary G. Tannen, Val Rice Univ Houston TX 77251 USA Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)9781450367127

distributed architectures for efficient processing of streaming data are increasingly critical to modern information processing systems. The goal of this paper is to develop type-based programming abstractions that facilitate correct and efficient deployment of a logical specification of the desired computation on such architectures. In the proposed model, each communication link has an associated type specifying tagged data items along with a dependency relation over tags that captures the logical partial ordering constraints over data items. The semantics of a (distributed) stream processing system is then a function from input data traces to output data traces, where a data trace is an equivalence class of sequences of data items induced by the dependency relation. This data-trace transduction model generalizes both acyclic synchronous data-flow and relational query processors, and can specify computations over data streams with a rich variety of partial ordering and synchronization characteristics. We then describe a set of programming templates for data-trace transductions: abstractions corresponding to common stream processing tasks. Our system automatically maps these high-level programs to a given topology on the distributed implementation platform Apache Storm while preserving the semantics. Our experimental evaluation shows that (1) while automatic parallelization deployed by existing systems may not preserve semantics, particularly when the computation is sensitive to the ordering of data items, our programming abstractions allow a natural specification of the query that contains a mix of ordering constraints while guaranteeing correct deployment, and (2) the throughput of the automatically compiled distributed code is comparable to that of hand-crafted distributed implementations.

关键词： distributed data stream processing types

来源：评论

学校读者我要写书评

暂无评论

SP-ant: An ant colony optimization based operator scheduler for high performance distributed stream processing on heterogeneous clusters

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期191卷 116322-116322页

作者： Farrokh, Mohammadreza Hadian, Hamid Sharifi, Mohsen Jafari, Ali Lab Univ Sci & Technol Distributed Syst Res Tehran Iran

A key feature of distributed stream processing (DSP) systems is the scheduling of operators on clustered computers. In scheduling, the assignment plan of operators to nodes of the cluster, requirements of operators, and the computational power of each worker node must be considered with the goal of finding a tradeoff between the communication latency of operators and the utilization of worker nodes to minimize the overall system response time. To reach this goal is quite challenging, especially in heterogeneous clusters, because there are no accurate estimations about the loads of worker nodes at run time. To address this challenge, we propose a novel stream processing scheduling using ant colony algorithm (SP-Ant). SP-Ant finds the best operator assignment plan considering the inter-node communication latencies of operators by initially collocating highly communicative operators on the same worker nodes using the bin-packing algorithm and iteratively (re-)scheduling only the less communicative operators using the exploration and exploitation phases of the evolutionary ant colony optimization (ACO) algorithm in order to reduce its convergence time. SP-Ant is implemented on the standard Apache Storm. Using several standard benchmark topologies of Storm, it is shown that SP-Ant outperforms the R-Storm and Storm default schedulers by at least 50% in reducing the response time.

关键词： Ant colony optimization distributed data stream processing Scheduling Apache Storm Heterogeneous clusters

来源：评论

学校读者我要写书评

暂无评论

Placement of distributed stream processing over heterogeneous infrastructures: doctoral symposium 16

Placement of distributed stream processing over heterogeneou...

引用

Proceedings of the 10th ACM International Conference on distributed and Event-based Systems

作者： Matteo Nardelli University of Rome Tor Vergata Italy

ISBN: (纸本)9781450340212

data stream processing (DSP) applications can extract, in a timely manner, valuable information from distributed data sources (e.g., sensing devices, social networks). These applications are subject to unpredictable and varying workloads and have to satisfy strict quality requirements, usually expressed in terms of latency, availability, and throughput. To successfully execute DSP applications, recent trends investigate the possibility of exploiting decentralized computing resources, which nonetheless pose new challenges due to the network and system heterogeneity, geographic distribution, and non-negligible network *** doctorate work, presented in this paper, investigates the deployment of DSP applications with Quality of Service (QoS) requirements over a distributed infrastructure of heterogeneous computing and networking resources. Specifically, to support our study, we extend an open-source DSP system, Apache Storm, by providing mechanisms for executing distributed QoS-aware placement policies and self-adaptation. Then, we provide a general formulation of the optimal placement problem for DSP applications, modeling the heterogeneity of the execution *** ongoing research aims at investigating the following directions. First, we will design heuristics able to determine the best placement in a feasible amount of time. Second, we will investigate runtime adaptation strategies and online placement algorithms. Third, to prove the generality of our approach, we will customize the designed solutions for similar problems (e.g., service selection, container deployment).

关键词： optimal placement distributed data stream processing quality of service

来源：评论

学校读者我要写书评

暂无评论

Online Parameter Optimization for Elastic data stream processing 6

Online Parameter Optimization for Elastic Data Stream Proces...

引用

Conference on 6th ACM Symposium on Cloud Computing (SoCC 2015)

作者： Heinze, Thomas Roediger, Lars Meister, Andreas Ji, Yuanzhen Jerzak, Zbigniew Fetzer, Christof SAP SE Weinheim Germany Univ Magdeburg D-39106 Magdeburg Germany Tech Univ Dresden Dresden Germany

ISBN: (纸本)9781450336512

Elastic scaling allows data stream processing systems to dynamically scale in and out to react to workload changes. As a consequence, unexpected load peaks can be handled and the extent of the overprovisioning can be reduced. However, the strategies used for elastic scaling of such systems need to be tuned manually by the user. This is an error prone and cumbersome task, because it requires a detailed knowledge of the underlying system and workload characteristics. In addition, the resulting quality of service for a specific scaling strategy is unknown a priori and can be measured only during runtime. In this paper we present an elastic scaling data stream processing prototype, which allows to trade off monetary cost against the offered quality of service. To that end, we use an online parameter optimization, which minimizes the monetary cost for the user. Using our prototype a user is able to specify the expected quality of service as an input to the optimization, which automatically detects significant changes of the workload pattern and adjusts the elastic scaling strategy based on the current workload characteristics. Our prototype is able to reduce the costs for three real-world use cases by 19% compared to a naive parameter setting and by 10% compared to a manually tuned system. In contrast to state of the art solutions, our system provides a stable and good trade-off between monetary cost and quality of service.

关键词： distributed data stream processing Load Balancing Elasticity Parameter Optimization

来源：评论

学校读者我要写书评

暂无评论

Supporting Fault-Tolerance in streaming Grid Applications 07

Supporting Fault-Tolerance in Streaming Grid Applications

引用

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Zhu, Qian Chen, Liang Agrawal, Gagan Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

No abstract available.

ISBN: (纸本)9781595936028

No abstract available.

关键词： Grid Computing Fault-Tolerance distributed data stream processing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：