集群文件服务系统中的负载均衡算法的研究

为解决目前集群文件服务系统中负载均衡算法的缺陷,充分考虑文件本身存在的差异,降低大文件分配到负载重的服务器上而造成负载失衡的可能性,避免频繁收集节点的负载信息造成大量额外的网络开销而降低系统吞吐量,提出了改进的负载均衡算法.该算法综合考虑文件负载量、服务器的硬件配置及其实时负载量,引入对上传文件大小和数量的计算,改变服务器负载量定时更新为定量更新.实验结果表明,该算法减少了客户的等待响应时间,提高了系统吞吐量,达到了良好的负载均衡.     

一种并行的多群蚁群算法研究与应用

针对蚁群算法易出现早熟收敛的缺陷,蚁群按照一定比例分解为具有启发信息的多种群,同时利用多核系统发挥蚁群算法并行性,提出一种并行的多群蚁群算法。该算法在初始化蚁群时产生带有启发信息的多种群,多种群采用多核系统并行处理方式相对独立求解最短路径。在求解过程中每个群体可分享路径信息,当某个种群求解到最短路径时即生成整个群体全局最短路径,从而保证种群多样性,算法求解速率及全局搜索均衡性。实验以Visual Studio2005中C＋＋编程实现仿真,结果表明此算法不但能有效求解GIS的最短路径,而且综合改善了算法性能。     

集群式流媒体服务器仿真系统的设计与实现

集群式流媒体服务器已经逐渐成为了高端流媒体服务器的主流.对集群式流媒体服务器资源优化配置和相关算法性能的研究都需要科学的仿真系统来协助完成.本文基于集群式流媒体服务器体系结构,利用已有的流媒体服务器实验床设计并实现了一套集群式流媒体服务器仿真系统.对仿真系统实验所得数据进行分析并给出了集群式流媒体服务器性能瓶颈和其资源优化配置的有益结论.     

蚁群算法在服务器集群批量任务调度中的应用

服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能.     

面向数据中心的虚拟机部署及优化算法

虚拟机动态配置是解决数据中心能耗低效的有效方法。针对动态配置过程中的虚拟机部署及优化问题展开研究,提出一种新的面向系统能耗的虚拟机部署算法以及基于主动迁移的优化策略。为了降低系统能耗,新算法采用基于服务器利用率的最佳适配降序算法求解虚拟机部署方案;同时为了适应应用负载的动态变化,新算法启动主动迁移策略对部署方案进行优化,即通过启发式算法在当前部署的基础上搜索使系统能耗更低的优化方案,并根据新部署对虚拟机执行主动迁移。考虑到迁移会导致应用服务质量降级和额外能耗,新算法通过在优化策略中设置基于服务器利用率的启动门限,对虚拟机主动迁移频率进行控制。仿真实验表明,所提算法在系统能耗、虚拟机迁移频率、服务器状态切换频率以及服务质量等多项性能指标上均有显著提高     

基于移动边缘计算的区块链计算资源分配和收益分享研究

针对移动终端设备本地计算资源有限的现状,提出了一种结合移动边缘计算机制的区块链系统.通过综合考虑系统中移动终端设备和边缘服务器的计算资源分配,以及移动终端设备的收益分配,提出了一个联合优化问题来最大化移动终端设备和边缘服务器的系统效用.为了快速求解该联合优化问题,设计了一种基于循环块坐标下降思想的多层分解算法.首先给定收益分享变量的值,通过对相应的子问题进行求解,得到移动终端设备以及边缘服务器的计算资源分配结果.然后把得到的结果作为固定的值继续求解移动终端设备的收益分享问题.最后,交替优化两部分变量直到算法收敛.仿真结果显示,所提算法能快速得到联合优化问题的最优解并有效提升区块链系统的系统效用.     

基于目标规划的服务器集群系统请求调度模型

研究网络服务器,提高传输质量问题,随着计算机网络的飞速发展,对服务器集群的请求也大量增加.针对服务器集群系统中负载分配问题,建立了一种基于目标规划的异构服务器集群系统请求调度模型.对请求按其自身性质进行分类,再将服务器本身的性能作为约束条件,并把请求丢失率最小和不同能力的服务器处理不同数目的请求作为目标,从而建立目标规划模型,通过模型求解来解决请求调度问题,并进行仿真实验.仿真结果验证了模型算法的有效性,模型算法既能让服务器处理能力得到较好发挥,又满足了请求响应时间的要求,使整个服务器集群的处理能力得到较大提高,为设计提供了有效的依据.     

面向数据挖掘的匿名化隐私数据发布系统设计

为了最大限度地保证隐私数据不被泄漏,设计并研发了面向数据挖掘技术的匿名化隐私数据发布系统。系统以Exynos 4412为主处理器,同时搭载μClinux操作系统,在处理数据的过程中实现并优化了多种经典匿名算法(如Incognito算法、Samariti算法、Datafly算法等),通过内置嵌入式Web服务器实现浏览器远程连接配置系统运行信息,并获取运行结果。同时,系统可以通过数据库的自定义配置及上传新增算法来实现数据的定制化发布。实验表明,系统算法执行效率高,能够有效地对发布数据进行隐私保护,为数据挖掘过程中的隐私泄漏问题提供了便捷可靠的解决方案。     

基于Amoeba中间件的分布式数据库管理系统

在数据库运用普遍建立于计算机网络之上的环境下,通过Amoeba中间件,实现对服务器集群的统一管理。该系统利用Amoeba中间件,通过对服务器信息的收集和修改,实现Amoeba服务器参数、MySQL数据库服务器参数、负载均衡、读写分离规则以及数据切分功能的配置。该系统避免了繁琐而杂乱的各个服务器独立配置,让管理人员从整体上掌控整个服务器系统运行状态。最后,实验验证,该套系统能够有效管理和配置服务器运行参数。     

基于排队网络的大型网络游戏服务器性能分析

介绍了大型网络游戏的服务器架构,基于架构提出了一个基于闭环排队网络的性能模型.给出了用平均值分析(MVA)求解该模型的算法,以及估计算法所需的性能参数的方法.模拟试验显示出,服务器系统的平均响应时间大致随着用户数量的增多成线性增长.通过模型计算出的结果与实验结果基本一致,从而验证了模型的有效性.     

Optimizing I/O server placement for parallel I/O on switch-based irregular networks

In this paper, we study I/O server placement for optimizing parallel I/O performance on switch-based clusters, which typically adopt irregular network topologies to allow construction of scalable systems with incremental expansion capability. Finding optimal solution to this problem is computationally intractable. We quantified the number of messages travelling through each network link by a workload function, and developed three heuristic algorithms to find good solutions based on the values of the workload function. The maximum-workload-based heuristic chooses the locations for I/O nodes in order to minimize the maximum value of the workload function. The distance-based heuristic aims to minimize the average distance between the compute nodes and I/O nodes, which is equivalent to minimizing average workload on the network links. The load-balance-based heuristic balances the workload on the links based on a recursive traversal of the routing tree for the network. Our simulation results demonstrate performance advantage of our algorithms over a number of algorithms commonly used in existing parallel systems. In particular, the load-balance-based algorithm is superior to the other algorithms in most cases, with improvement ratio of 10 to 95% in terms of parallel I/O throughput.     

Optimizing server placement in distributed systems in the presence of competition

Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server.Our major results include three parts. First, for tree-structured systems, we propose an O(|V|³k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with |V| nodes. We also propose an O(|V|³) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, called Greedy Add, Greedy Remove and Greedy Add-Remove, to solve them. Third, we show that if the number of requests a server can handle (i.e., server capacity) is bounded, the server placement problem is NP-complete even for tree networks. We then derive a variation of the same set of greedy heuristic algorithms, with consideration of server capacity constraint, to solve the problem.Our experiment results demonstrate that the greedy algorithms achieve good results, when compared with the upper bounds found by a linear programming algorithm. Greedy Add performs best in the unconstrained model, yielding a benefit within 12% difference from the theoretical upper bound in average. For the constrained model, Greedy Remove performs best for smaller network sizes, while Greedy Add-Remove performs best for larger network sizes. On average, the heuristic algorithms yield a benefit within 13% difference from the theoretical upper bound in the constrained model.     

基于patching的P2P VoD频道间协作策略

在P2P点播系统中,“冷播”频道往往节点较少且分布分散,各个节点形成多个独立的“播放链”,服务器往往需要为每个播放链单独提供一路数据流,负载很大。为此,提出了一种P2P VoD冷热播频道间协作策略,通过利用“热播”频道中具有富余服务能力的节点为“冷播”频道节点提供patching服务,从而连接“冷播”频道各个独立的“播放链”,进而减轻了多频道P2P点播系统中由于频道冷热播的不均衡导致“冷播”频道给服务器带来巨大的负载压力。仿真结果证明了该策略能有效提高多频道点播系统的并发服务能力。     

Lightweight Boolean Network Tomography Based on Partition of Managed Networks

Boolean network tomography is a promising technique to achieve fault management in networks where the existing IP-based troubleshooting mechanism cannot be used. Aiming to apply Boolean network tomography to fault management, a variety of heuristic methods for configuring monitoring trails and paths have been proposed to localize link failures in managed networks. However, these existing heuristic methods must be executed in a centralized server that administers the entire managed network and the methods present scalability problems when applied to large-scale managed networks. Thus, this paper proposes a novel scheme for achieving lightweight Boolean network tomography in a decentralized manner. The proposed scheme partitions the managed network into multiple management areas and localizes link failures independently within each area. This paper also proposes a heuristic network partition method with the aim of efficiently implementing the proposed scheme. The effectiveness of the proposed scheme is verified using typical fault management scenarios where all single-link failures and all dual-link failures are localized by the least number of monitoring paths on predetermined routes. Simulation results show that the proposed scheme can greatly reduce the computational load on the fault management server when Boolean network tomography is deployed in large-scale managed networks. Furthermore, the degradation of optimality in the proposed scheme can be mitigated in comparison with a centralized scheme that utilizes heuristics to reduce the computational load on the centralized server.     

P2P网络服务器部署方案及其启发式优化算法

为了更好地利用服务器提升P2P 网络的性能,提出了一种P2P 网络服务器最优化部署方案.该方案将如何部署有限的服务器资源来满足尽量多节点的问题,转化为一个带有约束条件的最优化问题.考虑到极坐标空间适合于表达长度相关的约束条件,例如部署方案中的约束条件,提出一种基于极坐标映射的启发式算法,解决P2P 网络服务器最优部署问题.相比于通常的使用罚函数的启发式算法,该算法可以有效地减小搜索空间,其性能的改善在搜索空间维数高的情况下更加显著.实验结果表明,所提出的服务器部署方案可以满足更多节点的需求,能够有效提高P2P 网络的性能.     

基于BDD的增量启发式搜索

增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法--BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.     

Optimizing server placement in hierarchical grid environments

In this paper, we address some problems related to server placement in Grid environments. Given a hierarchical network with requests from clients and constraints on server capability, the minimum server placement problem attempts to place the minimum number of servers that satisfy requests from clients. Instead of using a heuristic approach, we propose an optimal algorithm based on dynamic programming to solve the problem. We also consider the balanced server placement problem, which tries to place a given number of servers appropriately so that their workloads are as balanced as possible. We prove that an optimal server placement can be achieved by combining the above algorithm with a binary search on workloads. This approach can be further extended to deal with constrains on network capability. The simulation results clearly show the improvement in the number of servers and the maximum workload. Furthermore, as the maximum workload is reduced, the waiting time is reduced accordingly.

A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem

This paper presents a multiprocessor based heuristic algorithm for the Multi-dimensional Multiple Choice Knapsack Problem (MMKP). MMKP is a variant of the classical 0–1 knapsack problem, where items having a value and a number of resource requirements are divided into groups. Exactly one item has to be picked up from each group to achieve a maximum total value without exceeding the resource constraint of each type. MMKP has many real world applications including admission control in adaptive multimedia server system. Exact solution to this problem is NP-Hard, and hence is not feasible for real time applications like admission control. Therefore, heuristic solutions have been developed to solve the MMKP. M-HEU is one such heuristic, which solves the MMKP achieving a reasonable percentage of optimality. In this paper, we present a multiprocessor algorithm based on M-HEU, which runs in O(T/p+s(p)) time, where T is the time required by the algorithm using single processor, p is the number of processors and s(p), a function of p, is the synchronization overhead. We also present the worst-case analysis of our algorithm, the computation of the optimal number of processors as well as the lower bound of the total value that can be achieved by the heuristic.     

视频服务器网络中影像对象映射问题的研究

视频服务器网络中的影像对象映射问题是一种新的组合优化问题.服务器网络可以建立在基于局域网的工作站网络之上,也可以建立在广域网之上.基于对用户的服务请求模式、服务器网络的存储容量和通信带宽等因素的综合考虑,研究了服务器网络中影像对象映射问题,利用局部搜索算法给出了一套对该映射问题的解决方案.然后用一套基准集实例对给出的算法集进行验证.结果表明,在较短的计算时间内,该算法可以得到近似最优解的方案.     

Performance analysis of a pull-based parallel video server

In conventional video-on-demand systems, video data are stored in a video server for delivery to multiple receivers over a communications network. The video server's hardware limits the maximum storage capacity as well as the maximum number of video sessions that can concurrently be delivered. Clearly, these limits will eventually be exceeded by the growing need for better video quality and larger user population. This paper studies a parallel video server architecture that exploits server parallelism to achieve incremental scalability. First, unlike data partition and replication, the architecture employs data striping at the server level to achieve fine-grain load balancing across multiple servers. Second, a client-pull service model is employed to eliminate the need for interserver synchronization. Third, an admission-scheduling algorithm is proposed to further control the instantaneous load at each server so that linear scalability can be achieved. This paper analyzes the performance of the architecture by deriving bounds for server service delay, client buffer requirement, prefetch delay, and scheduling delay. These performance metrics and design tradeoffs are further evaluated using numerical examples. Our results show that the proposed parallel video server architecture can be linearly scaled up to more concurrent users simply by adding more servers and redistributing the video data among the servers