An efficient partitioning algorithm for distributed virtualenvironment systems

Distributed virtual environment (DVE) systems model and simulate the activities of thousands of entities interacting in a virtual world over a wide area network. Possible applications for DVE systems are multiplayer video games, military and industrial trainings, and collaborative engineering. In general, a DVE system is composed of many servers and each server is responsible to manage multiple clients who want to participate in the virtual world. Each server receives updates from different clients (such as the current position and orientation of each client) and then delivers this information to other clients in the virtual world. The server also needs to perform other tasks, such as object collision detection and synchronization control. A large scale DVE system needs to support many clients and this imposes a heavy requirement on networking resources and computational resources. Therefore, how to meet the growing requirement of bandwidth and computational resources is one of the major challenges in designing a scalable and cost-effective DVE system. In this paper, we propose an efficient partitioning algorithm that addresses the scalability issue of designing a large scale DVE system. The main idea is to dynamically divide the virtual world into different partitions and then efficiently assign these partitions to different servers. This way, each server will process approximately the same amount of workload. Another objective of the partitioning algorithm is to reduce the server-to-server communication overhead. The theoretical foundation of our dynamic partitioning algorithm is based on the linear optimization principle. We also illustrate how one can parallelize the proposed partitioning algorithm so that it can efficiently partition a very large scale DVE system. Lastly, experiments are carried out to illustrate the effectiveness of the proposed partitioning algorithm under various settings of the virtual world     

基于业务抽象规划的分布式动态服务组合算法

异构系统间难以实现计算资源的灵活共享,制约分布式信息系统性能的提升,基于面向服务架构的Web服务技术,为异构系统计算资源共享提供了有效手段。为此,针对Web服务组合在集中式发布架构下单点故障和性能瓶颈问题,提出一种基于业务抽象规划的分布式动态服务组合算法。该算法根据组合规划结果对业务抽象规划库进行动态扩充,快速组合出满足需求的服务,逐步提高服务组合响应率。仿真结果表明,该算法在分布式环境下可减少服务请求过程中交互的信息量,降低请求响应时间,提高服务组合效率。     

Improving the performance of distributed virtual environment systems

The last years have witnessed a dramatic growth in the number as well as in the variety of distributed virtual environment systems. These systems allow multiple users, working on different client computers that are interconnected through different networks, to interact in a shared virtual world. One of the key issues in the design of scalable and cost-effective DVE systems is the partitioning problem. This problem consists of efficiently assigning the existing clients to the servers in the system and some techniques have been already proposed for solving it. This paper experimentally analyzes the correlation of the quality function proposed in the literature for solving the partitioning problem with the performance of DVE systems. Since the results show an absence of correlation, we also propose the experimental characterization of DVE systems. The results show that the reason for that absence of correlation is the nonlinear behavior of DVE systems with regard to the number of clients in the system. DVE systems reach saturation when any of the servers reaches 100 percent of CPU utilization. The system performance greatly decreases if this limit is exceeded in any server. Also, as a direct application of these results, we present a partitioning method that is targeted to keep all the servers in the system below a certain threshold value of CPU utilization, regardless of the amount of network traffic. Evaluation results show that the proposed partitioning method can improve DVE system performance, regardless of both the movement pattern of clients and the initial distribution of clients in the virtual world.     

A comparison study of evolutive algorithms for solving the partitioning problem in distributed virtual environment systems

Fast Internet connections and the widespread use of high performance graphic cards are making Distributed Virtual Environment (DVE) systems very common nowadays. However, there are several key issues in these systems that should still be improved in order to design a scalable and cost-effective system. One of these key issues is the partitioning problem. This problem consists of efficiently assigning clients (3D avatars) to the servers in the system. In this paper, we present a comparison study of different modern heuristics for solving the partitioning problem in DVE systems, as an alternative to the ad hoc heuristic proposed in the literature. Performance evaluation results show that some of the heuristic methods can greatly improve the performance of the partitioning method, particularly for large DVE systems. In this way, efficiency and scalability of DVE systems can be significantly improved.     

面向多自治域网格的信息服务模型及其实现

网格是实现分布异构资源共享的有效模式,而信息服务实现系统服务与资源的有效管理,是网格系统的重要组成部分.ChinaGrid是由多个自治域组成的大规模网格,现有的信息服务不能满足此类系统特性与应用需求.文中提出网格信息服务体系GISA2.0,强化了域自治管理和资源信息的安全性.GISA2.0实现了可扩展的网格信息模型和面向服务、支持多种监控信息聚集的层次化信息管理框架.提出了基于分布XPath引擎的多域资源信息检索机制,实现了安全、快速和用户相关的虚拟全局资源视图.     

一种新型分布式元数据管理策略

高效、可扩展的元数据管理系统是提高分布式存储系统整体性能的关键. 传统的元数据分配策略会导致元数据负载不均衡,以及在多进程资源抢占的情况下,会存在响应处理用户请求效率不高,存储文件数目受限等问题. 上述问题在高并发、低延迟的数据存储需求中尤为突出. 提出了一个基于一致性Hash与目录树的元数据管理策略,并实现了相应的分布式元数据管理系统：利用负载均衡算法,对元数据进行迁移,保证了粗粒度负载信息收集,细粒度调整的均衡策略. 多项实验的结果表明,该策略能实现元数据负载均衡,降低用户请求处理延迟,提高分布式系统的可扩展性和可用性.     

P2P工作流系统的调度框架设计和实现

为了把参与者信息用于业务流程调度,同时给出基于流程实例迁移服务的一个可扩展性强的调度框架,提出了一个在P2P工作流系统上的流程实例调度框架.通过在框架中加入一个根据参与者位置调度的算法和一个负载均衡算法,证实了该框架的确能够针对业务流程的不同特点进行决策从而提高流程实例的执行效率.通过网页绑定服务和参与者绑定服务保证流程迁移后能继续和业务系统交互,表明了调度框架的实用性.     

分布式虚拟环境

分布式虚拟环境是单用户虚拟环境网络化、多用户化的发展。其运行在多台计算机上,这些计算机通过网络进行连接,用户通过使用计算机实时交互,共享相同的虚拟世界。该文首先阐述了分布式虚拟环境的基本概念和特征,并在此基础上简要介绍了两种常用的分布式虚拟环境的模型结构;然后从底层介绍了分布式虚拟环境中的DIS协议,并从高层描述了相关的虚拟现实技术;最后展望了分布式虚拟环境的应用前景。     

Skyframe: a framework for skyline query processing in peer-to-peer systems

This paper looks at the processing of skyline queries on peer-to-peer (P2P) networks. We propose Skyframe, a framework for efficient skyline query processing in P2P systems, which addresses the challenges of quick response time, low network communication cost and query load balancing among peers. Skyframe consists of two querying methods: one is optimized for network communication while the other focuses on query response time. These methods are different in the way in which the query search space is defined. In particular, the first method uses a high dominating point that has a large dominating region to prune the search space to achieve a low cost in network communication. On the other hand, the second method relaxes the search space in order to allow parallel query processing to speed up query response. Skyframe achieves query load balancing by both query load conscious data space splitting/merging during the join/departure of nodes and dynamic load migration. We further show how to apply Skyframe to both the P2P systems supporting multi-dimensional indexing and the P2P systems supporting single-dimensional indexing. Finally, we have conducted extensive experiments on both real and synthetic data sets over two existing P2P systems: CAN (Ratnasamy in A scalable content-addressable network. In: Proceedings of SIGCOMM Conference, pp. 161–172, 2001) and BATON (Jagadish et al. in A balanced tree structure for peer-to-peer networks. In: Proceedings of VLDB Conference, pp. 661–672, 2005) to evaluate the effectiveness and scalability of Skyframe.     

基于迁移技术的云资源动态调度策略研究

现有云资源管理平台存在着瞬时资源利用率峰值易引发迁移、动态负载效果不佳等问题。依据云资源动态调度模型,提出了有效的基于迁移技术的虚拟机动态调度算法。算法将物理节点负载与虚拟机迁移损耗评估、多次触发控制、目标节点定位三者有机结合,实现云计算数据中心高效的动态负载均衡。实验结果表明,该算法优于CloudSim的DVFS调度策略,在保证应用服务水平的同时能减少虚拟机迁移次数和物理机启用数量。     

用于教育资源管理的网格文件系统

基于Internet的远程教育是当今及未来教育的一种重要途径，它需要管理大量的教育资源及用户。在这样一个网格环境下，需要有一个具有高可扩展性、具有动态复制的分布式文件共享途径。该文在回顾了文件共享方面的相关工作之后，提出了一种基于Web的分布式文件管理架构——网格文件系统(GridFS)。描述了它的拓扑结构及文件访问服务和元信息服务。GridFS对许多网格应用、数字图书馆的互联和多级Web Cache系统是有益的。     

广域网分布式虚拟环境中的动态因果消息序控制方法

在广域网运行的分布式虚拟环境中,由于消息传输延迟较大,因果消息序的一致性控制效果同时由因果序的正确性和实时性两方面决定。针对分布式虚拟环境消息序维护方法必须动态平衡因果序正确性和实时性的问题,提出了一种新的因果消息序控制方法,能够动态地调节和平衡分布式虚拟环境中各节点阻塞的结果事件数与延迟的原因事件数,满足因果消息处理的正确性和实时性需求。实验结果表明,与现有方法相比,该方法能够在保证实时性的同时,有效提高因果序维护的正确程度,为广域网分布式虚拟环境的消息序维护提供有力支撑。     

Artificial immune system inspired behavior-based anti-spam filter

This paper proposes a novel behavior-based anti-spam technology for email service based on an artificial immune-inspired clustering algorithm. The suggested method is capable of continuously delivering the most relevant spam emails from the collection of all spam emails that are reported by the members of the network. Mail servers could implement the anti-spam technology by using the “black lists” that have been already recognized. Two main concepts are introduced, which defines the behavior-based characteristics of spam and to continuously identify the similar groups of spam when processing the spam streams. Experiment results using real-world datasets reveal that the proposed technology is reliable, efficient and scalable. Since no single technology can achieve one hundred percent spam detection with zero false positives, the proposed method may be used in conjunction with other filtering systems to minimize errors.     

密码云中基于熵权评价的虚拟密码机调度方法

针对密码云系统的负载均衡问题,提出了一种基于熵权评价的虚拟密码机调度方法（VSMEWE）。为提高密码服务质量、高效利用密码运算资源,以云密码机的CPU、内存、网络带宽和密码卡吞吐带宽等资源的利用率为主要指标评价云密码机的资源状态,根据云密码机的综合评价值比较结果,得出虚拟密码机的迁移选择方案。实验结果表明,所提算法与Entropy算法和Baseline算法相比,具有全局性和时效性,提高了系统负载均衡效果,执行效率也分别提高了6.8%和22.7%。     

MMOG中的一种动态负载共享算法*

针对MMOG中的服务器超载问题,提出一种动态负载共享算法,使得一个超载的服务器能够方便地将它的一部分负载迁移到没有超载的服务器上.同时在基于预订区域概念的基础上,通过扩大邻居服务器的范围,提出一种客户端迁移方案来减少该算法的开销,从而提高系统的响应速度和性能.     

On the Design of Adaptive and Decentralized Load Balancing Algorithms with Load Estimation for Computational Grid Environments

In this paper, we address several issues that are imperative to grid environments such as handling resource heterogeneity and sharing, communication latency, job migration from one site to other, and load balancing. We address these issues by proposing two job migration algorithms, which are MELISA (modified ELISA) and LBA (load balancing on arrival). The algorithms differ in the way load balancing is carried out and is shown to be efficient in minimizing the response time on large and small-scale heterogeneous grid environments, respectively. MELISA, which is applicable to large-scale systems (that is, interGrid), is a modified version of ELISA in which we consider the job migration cost, resource heterogeneity, and network heterogeneity when load balancing is considered. The LBA algorithm, which is applicable to small-scale systems (that is, intraGrid), performs load balancing by estimating the expected finish time of a job on buddy processors on each job arrival. Both algorithms estimate system parameters such as the job arrival rate, CPU processing rate, and load on the processor and balance the load by migrating jobs to buddy processors by taking into account the job transfer cost, resource heterogeneity, and network heterogeneity. We quantify the performance of our algorithms using several influencing parameters such as the job size, data transfer rate, status exchange period, and migration limit, and we discuss the implications of the performance and choice of our approaches.     

A scalable multi-attribute hybrid overlay for range queries on the cloud

Cloud computing has become a promising paradigm as next generation computing model, by providing computation, software, data access, and storage services that do not need to know the location of physical resources interconnected across the globe providing such services. In such an environment, important issues as information sharing and resource/service discovery arise. In order to overcome critical limitations in centralized approaches for information sharing and resource/service discovery, this paper proposes a framework of a scalable multi-attribute hybrid overlay featured with decentralized information sharing, flexible resource/service discovery, fault tolerance and load balancing. Additionally, the proposed hybrid overlay integrates a structured P2P system with an unstructured one to support complex queries. Mechanisms such as load balancing and fault tolerance implemented in our proposed system to improve the overall system performance are also discussed. Experimental results show that the performance of the proposed approach is feasible and stable, as the proposed hybrid overlay improves system performance by reducing the number of routing hops and balancing the load by migrating requests.     

An agent-based approach for dynamic adjustment of scheduled jobs in computational grids

Grid computing is a newly developed technology for complex systems with large-scale resource sharing, wide-area communication, and multi-institutional collaboration. Grid scheduling is an important infrastructure in the grid computing environment. Most of the existing grids scheduling methods focus on maximizing processor utilization without taking grid load into consideration. This may lead to significant inefficiencies in performance such as large job queues and processing delays. In this paper, we propose a multiagent-based scheduling system for computational grids with a new approach. Agent technology is suitable for a computational grid because of the dynamic, heterogeneous, and autonomous nature of the grid. The main idea of the proposed system is a combination of a static scheduling using a fixed scheduling algorithm and a dynamic adjustment through the autonomous behavior of agents. The superiority of the proposed system, in reducing the load of the grid and minimizing the response time for executing user applications, is demonstrated by simulation experiments.     

面向Web Service的动态负载均衡设计与实现

负载均衡是分布式系统的资源管理模块,它的主要功能是合理和透明地在服务器之间分配系统负载,以达到系统的综合性能最优。基于中间件的负载均衡技术在整合异构系统、透明访问和扩展能力等方面具有优势。在中间模块上可以灵活实现多种负载均衡算法,来调整和满足不同应用的负载均衡需求,提高系统的扩展性、配置性、健壮性。本文参考分布式系统中的模型,构建了基于Web Service的负载均衡器,实现了动态负载均衡调度策略。为了准确地描述系统的负载,选择CPU利用率、内存利用率、系统响应时间、输入输出流量和进程数作为衡量系统负载的参量;为了避免因监测服务器而加大均衡器的压力,策略中将负载信息采集程序运行在机群内的各服务结点上,当相邻采集周期的负载差值超过标准值后调用均衡器上的Web服务,报告自身的负载状况,使均衡器根据负载信息进行同步操作,更换服务序列。最后通过仿真实验证明本策略在异构Web平台中具有可行性。     

基于缓冲Cell的用户迁移方法研究

分布式虚拟环境中现有的用户迁移方法主要基于固定缓冲区,而近年研究热点的多服务器结构采用动态缓冲区,服务器区域调整中受影响的用户不能进行迁移,影响了交互性和效率.提出一种基于缓冲Cell的用户迁移方法,将缓冲区用一组Cell来表示,将用户替身运动和区域调整引起的迁移抽象为4项状态迁移条件.根据用户和所属Cell的状态变化,触发用户状态迁移,多个用户可并发高效地完成迁移.实验表明,这种用户迁移方法可有效支持用户的并发迁移,并具有较低的通信附加负载.