网络并行计算中的负载平衡

本文详细讨论了网络并行计算中的负荷平衡，尤其是动态负载平衡问题，并提出了相应的解决办法，最后，我们给出了如何在Ｅｘｐｒｅｓｓ环境中进行负载平衡程序设计的方法。     

分布式系统中网络负载平衡的研究

分布式系统可以有效地减少处理瓶颈,其具有较强的容错能力,得到了相当广泛的研究和应用。本文介绍了分布式系统的定义和负载平衡技术,其中重点讨论了动态负载平衡的策略。最后,根据分布式应用的特点,提出了一种分布式系统网络负攀平衡的解决方案,并给出了算法描述和模型。     

数据收集传感器网络的负载平衡网络构建方法

传感器网络所具有的集中式数据收集、多跳数据传输、多对一流量模式这3种特征会造成漏斗效应的出现,这会导致严重的包碰撞、网络拥塞、包丢失,甚至拥塞崩溃,还会导致能量消耗的热点的出现,使某些节点甚至整个网络过早死亡.负载平衡技术能够有效缓解漏斗效应的产生.针对静态数据收集传感器网络,基于供求网络的思想,提出了一种分布式算法,将传感器节点组织成交易平衡网络,用于平衡传感器节点的负载.利用这种方法组织而成的网络结构不是一棵负载平衡树,而是一个负载平衡网络.实验结果验证了这种方法的有效性.     

互连网络局部迭代负载平衡技术

新的基于网络的计算模式（如网格计算,云计算,P2P计算）的共同特点是计算节点之间都是通过互连网络进行通信。对互连网络各个计算节点产生的工作负载进行平衡是提高计算系统性能的关键。文章介绍了近年来在互连网络上使用局部迭代方式求解负载平衡问题在算法设计及其性能分析反面的若干基本研究成果。     

基于遗传模拟退火算法的网络负载平衡研究

介绍了网络负载平衡的基本算法,建立了负载平衡的数学模型,重点阐述了遗传算法和模拟退火算法相结合的重要意义。并提出将遗传模拟退火算法应用于解决网络负载平衡问题的算法,通过实例证明了其有效性。     

负载平衡静态分析方法及其在网络路由分配中的应用

在大规模并行处理系统ＭＰＰ和工作站机群中，普遍存在着负载分配问题。能否在多个同构处理单元或多个异构处理机（或工作站）之间有效地平衡各负载，是决定能否充分发掘整个系统并行性，进而提高整个系统性能的关键问题之一。本文提出了负载平衡问题的数学模型及使用ＭＴＲＳＡ进行负载平衡静态分析的方法，给出了任务及通信关系的形式化描述及实验分析结果。最后，作者将上述模型及ＭＴＲＳＡ应用于网络路由分配方法之中。     

DiffServ MPLS网络中的负载平衡

简要介绍了多协议标记交换协议MPLS与区分服务DiffServ ,分析了MPLS与DiffServ相结合对网络的设计和控制带来的影响。并在此基础上 ,提出了一种动态负载平衡的方法 ,将DiffServ几种业务在多条LSP上平衡传输。仿真试验表明 ,大大降低了延迟和队长 ,提高了吞吐量     

ATM网络拥塞预防的动态负载平衡策略

讨论了拥塞预防在ＡＴＭ网络中的必要性以及拥塞预防的关键性要素,并利用公式系统中并行计算的动态负载平衡的思想,提出了ＡＴＭ网络中负载的概念,给出了ＡＴＭ网络拥塞预防的算法。     

在WINDOWS 2000上实现网络负载平衡

随着Internet和Intranet的高速发展，基于IP的应用成为网络最普遍、最有用甚至是必不可少的部分。网络负载平衡提高了运行在诸如Web服务器、FTP服务器和其它关键任务服务器上的因特网服务器程序的可用性和可伸缩性。文章介绍了Win200网络负载平衡的解决方案。     

Load balancing aware scheduling algorithms for fog networks

Fog networks have attracted the attention of researchers recently. The idea is that a part of the computation of a job/application can be performed by fog devices that are located at the network edge, close to the users. Executing latency sensitive applications on the cloud may not be feasible, owing to the significant communication delay involved between the user and the cloud data center (cdc). By the time the application traverses the network and reaches the cloud data center, it might already be too late. However, fog devices, also known as mobile data centers (mdcs), are capable of executing such latency sensitive applications. In this paper, we study the problem of balancing the application load while taking account of security constraints of jobs, across various mdcs in a fog network. In case a particular mdc does not have sufficient capacity to execute a job, the job needs to be migrated to some other mdc. To this end, we propose three heuristic algorithms: minimum distance, minimum load, and minimum hop distance and load (MHDL). In addition, we also propose an ILP-based algorithm called load balancing aware scheduling ILP (LASILP) for solving the task mapping and scheduling problem. The performance of the proposed algorithms have been compared with the cloud only algorithm and another heuristic algorithm called fog-cloud-placement (FCP). Simulation results performed on real-life workload traces reveal that the MHDL heuristic performs better as compared to other scheduling policies in the fog computing environment while meeting application privacy requirements.     

Load balancing for video streaming services in hierarchical wireless networks

Wireless networks have focused on voice call services or wireless Internet access services. These days, the application service domain of wireless networks is rapidly expanding, and a wide variety of new services is emerging. Video streaming service is one of the most promising examples, evidenced by 3GPP’s MBMS (Multimedia Broadcast Multicast Service) and IMS (IP Multimedia Subsystem). In this paper, we consider the provision of video streaming services in hierarchical wireless networks with multiple layers of cells. We particularly focus on optimal load balancing among the cells, aiming at the minimization of frame drop ratio for given video streaming sessions. From this objective function, we derive the optimal load balancing condition. Load balancing is essentially the issue of which users are assigned to which cell, i.e., the user assignment problem. In our user assignment algorithm, we compute thresholds to divide users into groups according to the user characteristics, and map the user groups to proper cells. The optimal load balancing condition can be reached by adaptively adjusting the threshold at run time. This process does not require prior knowledge about the system status, such as the system capacity or user traffic requests, which warrants the practicality of the proposed scheme. Via simulations, we demonstrate that the proposed scheme achieves optimal load balancing in various realistic environments.     

一种适用于Ad hoc网络的基于概率负载均衡算法

为解决移动自组织网络(MANET)中网络拥塞导致的网络时延增大和吞吐量下降, 提出一种基于概率的负载均衡算法, 节点利用历史负载信息映射网络负载状态, 用概率算法进行路由准入, 从而完成负载均衡。基于历史状态的负载映射有效解决了分布式独立运算中存在的负载状态判断困难等问题, 概率算法能有效克服门限准入法则存在的模糊判别问题, 同时大量减少广播包的洪泛, 节省信道资源。结合经典的按需路由协议, 设计了H&P_DSR(history and probability based dynamic source routing)协议。仿真和理论分析一致表明, 该负载均衡算法能够准确有效地对网络负载进行均衡, H&P_DSR协议在没有增加任何信道开销的情况下显著提高了网络吞吐量, 降低了时延。     

Load balancing and routing on the hypercube and related networks

Several results related to the load balancing problem on the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly are shown. Implications of these results for routing algorithms are also discussed. Our results include the following:

• Efficient load balancing algorithms are found for the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly.

• Load balancing is shown to require more time on a p-processor shuffle-exchange, cube-connected cycle or butterfly than on a p-processor weak hypercube.

• Routing n packets on a p-processor hypercube can be done optimally whenever n = p^1+1/k, for any fixed k > 0.

     

MPLS网络的故障管理

研究了MPLS网络的故障管理。MPLS非光网络的数据平面和控制平面共享传输媒质,而光网络中数据平面和控制平面并非紧密地结合在一起,甚至不一定具有相同的拓扑,这就导致了两种网络在故障管理时存在很大差异。分析了MPLS非光网络与光网络的故障管理的区别,为MPLS非光网络设计并实现了一种LDP会话重建方案。     

Load balancing in project assignment

In this paper, we study a project assignment problem. Specifically, a set of projects, each of which needs to be finished over a project development cycle, are to be assigned to a group of identical engineers over a discrete planning horizon. The workload of the projects is different and fluctuates over their development cycles. In each period, engineers have a maximum allowed workload. The objective of the problem is to assign the projects to engineers with the objective of balancing the total workload among the engineers; the load balance is measured by the difference between the maximum and the minimum total workload. Such a problem is new to the literature. After proving the problem is strongly NP-hard, we propose a two-stage heuristic approach to solve it. Extensive numerical experiments show that the proposed approach can achieve optimal or nearly optimal solutions for all test cases; such performance is much better than what can be obtained from an IP model solved with ILOG CPLEX. An analysis of the algorithm has also been provided to explain how the superior performance has been achieved.     

Load balancing of dynamical distribution networks with flow constraints and unknown in/outflows

We consider a basic model of a dynamical distribution network, modeled as a directed graph with storage variables corresponding to every vertex and flow inputs corresponding to every edge, subject to unknown but constant inflows and outflows. As a preparatory result it is shown how a distributed proportional–integral controller structure, associating with every edge of the graph a controller state, will regulate the state variables of the vertices, irrespective of the unknown constant inflows and outflows, in the sense that the storage variables converge to the same value (load balancing or consensus). This will be proved by identifying the closed-loop system as a port-Hamiltonian system, and modifying the Hamiltonian function into a Lyapunov function, dependent on the value of the vector of constant inflows and outflows. In the main part of the paper the same problem will be addressed for the case that the input flow variables are constrained to take value in an arbitrary interval. We will derive sufficient and necessary conditions for load balancing, which only depend on the structure of the network in relation with the flow constraints.     

使用蚁群优化的WMSNs负载均衡路由方案

由于无线多媒体传感器网络（WMSNs）具有资源受限、信道容量可变、数据冗余度高等特点,研究WMSNs的QoS 路由具有极大的挑战性。针对上述问题,提出了一种使用蚁群优化的WMSNs负载均衡路由方案——ACOLBR。ACOLBR采用分簇技术进行区域划分,簇间利用ACO找到一条簇首到基站的最优路径,簇内利用以簇首为根节点的最小生成树算法组织路由。仿真结果表明,与AGRA和M-IAR算法相比,ACOLBR在负载均衡、传输时延、传输成功率、可扩展性和自适应性等方面均有较大改进,实现了全网的负载均衡,有效地延长了网络生命期,保证了网络传输的QoS。     

Load balancing in large-scale RFID systems

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers — how should a given set of tags be assigned to readers such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We first present centralized solutions to two different variants of this load balancing problem: (i) min–max cost assignment (MCA), and (ii) min–max tag count assignment (MTA). We show that MCA, the generalized variant of the load balancing problem, is NP-hard and hence present a 2-approximation algorithm for it. We next present an optimal centralized solution for MTA, an important specialized variant of the problem. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.