Properties of a hierarchical network based on the star graph

This paper introduces a new class of interconnection networks named star-pyramid. An n-level star-pyramid is formed by piling up star graphs of dimensions 1 to n in a hierarchy, connecting any node in each i-dimensional star, 1 < i ? n, to a node in the (i − 1)-dimensional star whose index is reached by removing the i symbol from the index of the former node in the i-dimensional star graph. Having extracted the properties of the new topology, featuring topological properties, a minimal routing algorithm, a simple but efficient broadcast algorithm, Hamiltonicity and pancyclicity, we then compare the network properties of the proposed topology and the well-known pyramid topology. We show that the star-pyramid has some more attractive properties than its equivalent pyramid. Finally, we propose two variants of star-pyramid, namely the generic star-pyramid and wrapped star-pyramid, as topologies with improved scalability, fault-tolerance, and diameter.     

The load balancing problem in OTIS-Hypercube interconnection networks

An interconnection network architecture that promises to be an interesting option for future-generation parallel processing systems is the OTIS (Optical Transpose Interconnection System) optoelectronic architecture. Therefore, all performance improvement aspects of such a promising architecture need to be investigated; one of which is load balancing technique. This paper focuses on devising an efficient algorithm for load balancing on the promising OTIS-Hypercube interconnection networks. The proposed algorithm is called Clusters Dimension Exchange Method (CDEM). The analytical model and the experimental evaluation proved the excellence of OTIS-Hypercube compared to Hypercube in terms of various parameters, including execution time, load balancing accuracy, number of communication steps, and speed.

Efficient network isolation and load balancing in multi-tenant HPC clusters

Multi-tenancy promises high utilization of available system resources and helps maintaining cost-effective operations for service providers. However, multi-tenant high-performance computing (HPC) infrastructures, like dynamic HPC clouds, bring unique challenges, both associated with providing performance isolation to the tenants, and achieving efficient load-balancing across the network fabric. Each tenant should experience predictable network performance, unaffected by the workload of other tenants. At the same time, it is equally important that the network links are balanced, avoiding network saturation. The network saturation can lead to unpredictable application performance, and a potential loss of profit for the cloud service providers.In this paper, we present two significant extensions to our previously proposed partition-aware fat-tree routing algorithm, pFTree, for InfiniBand-based HPC systems. First, we extend pFTree to incorporate provider defined partition-wise policies that govern how the nodes in different partitions are allowed to share network resources with each other. Second, we present a weighted version of the pFTree routing algorithm, that besides partitions, also takes node traffic characteristics into account to balance load across the network links more evenly. A comprehensive evaluation comprising both real-world experiments and simulations confirms the correctness and feasibility of the proposed extensions.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

An accurate mathematical performance model of adaptive routing in the star graph

Analytical modelling is indeed the most cost-effective method to evaluate the performance of a system. Several analytical models have been proposed in the literature for different interconnection network systems. This paper proposes an accurate analytical model to predict message latency in wormhole-switched star graphs with fully adaptive routing. Although the focus of this research is on the star graph but the approach used for modelling can be, however, used for modelling some other regular and irregular interconnection networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy for various network sizes and under different operating conditions.     

A study of fault tolerance in star graph

The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn.     

Diagnosability of star graphs under the comparison diagnosis model

In this paper, the diagnosability of n-dimensional star graph Sn under the comparison diagnosis model has been studied. It is proved that Sn is (n−1)-diagnosable under the comparison diagnosis model when n?4.     

THE LOAD DISTRIBUTION PROBLEM IN A PROCESSOR RING

Abstract

Given a global picture of the system load and the average load, the load distribution problem is to find a suitable schedule, consisting of the amount of excess load to transfer along every edge, so that the system load can be balanced in minimal time by executing the schedule. We study this problem for the ring topology We discuss some existing algorithms, show how they fall short of being able to generate optimal schedules, and present a simple algorithm that would generate an optimal schedule for any given system load instance. This simple algorithm relies on an existing algorithm to create a search window in which the optimal solution is to be found.     

Edge-bipancyclicity of star graphs with faulty elements

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S_n. Given a set F comprised of faulty vertices and/or edges in S_n with |F|≤n−3 and any fault-free edge e in S_n−F, we show that there exist cycles of every even length from 6 to n!−2|F_v| in S_n−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite S_n is n!−2|F_v| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|F_v|+2 to n!−2|F_v| can be embedded.     

基于服务器实时性能状态的动态负载均衡算法

为实现Web服务器集群合理的作业任务分配,文章提出了一种新的负载均衡算法,综合考虑了负载均衡调度器后端的业务主机的实时性能,实现了负载均衡调度的动态调整.     

Online vector scheduling and generalized load balancing

We give a polynomial time reduction from the vector scheduling problem (VS) to the generalized load balancing problem (GLB). This reduction gives the first non-trivial online algorithm for VS where vectors come in an online fashion. The online algorithm is very simple in that each vector only needs to minimize the _Lln(md)$L_{ln\left(md\right)}$ norm of the resulting load when it comes, where m$m$ is the number of partitions and d$d$ is the dimension of vectors. It has an approximation bound of elog(md)$elog\left(md\right)$, which is in O(ln(md))$O(ln\left(md\right))$, so it also improves the O(ln²d)$O\left({ln}^{2}d\right)$ bound of the existing polynomial time algorithm for VS. Additionally, the reduction shows that GLB does not have constant approximation algorithms that run in polynomial time unless P=NP$P=NP$.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Practical load balancing for content requests in peer-to-peer networks

This paper studies the problem of balancing the demand for content in a peer-to-peer network across heterogeneous peer nodes that hold replicas of the content. Previous decentralized load balancing techniques in distributed systems base their decisions on periodic updates containing information about load or available capacity observed at the serving entities. We show that these techniques do not work well in the peer-to-peer context; either they do not address peer node heterogeneity, or they suffer from significant load oscillations which result in unutilized capacity. We propose a new decentralized algorithm, Max-Cap, based on the maximum inherent capacities of the replica nodes. We show that unlike previous algorithms, it is not tied to the timeliness or frequency of updates, and consequently requires significantly less update overhead. Yet, Max-Cap can handle the heterogeneity of a peer-to-peer environment without suffering from load oscillations. Mema Roussopoulos is an Assistant Professor of Computer Science on the Gordon McKay Endowment at Harvard University. Before joining Harvard, she was a Postdoctoral Fellow in the Computer Science Department at Stanford University. She received her PhD and Master’s degrees in Computer Science from Stanford, and her Bachelor’s degree in Computer Science from the University of Maryland at College Park. Her interests are in the areas of distributed systems, networking, and mobile and wireless computing. Mary Baker is a Senior Research Scientist at HP Labs. Her research interests include distributed systems, networks, mobile systems, security, and digital preservation. Before joining HP Labs she was on the faculty of the computer science department at Stanford University where she ran the MosquitoNet project. She received her PhD from the University of California at Berkeley.     

A topology-aware load balancing algorithm for clustered hierarchical multi-core machines

In this paper, we present a topology-aware load balancing algorithm for parallel multi-core machines and its proof of asymptotic convergence to an optimal solution. The algorithm, named HwTopoLB, aims to improve the application performance by reducing core idleness and communication delays. HwTopoLB was designed taking into account the properties of current parallel systems composed of multi-core compute nodes, namely their network interconnection, and their complex and hierarchical core topology. The latter comprises multiple levels of cache, and a memory subsystem with NUMA design. These systems provide high processing power at the expense of asymmetric communication costs, which can hamper the performance of parallel applications depending on their communication patterns if ignored. Our load balancing algorithm models asymmetries in terms of latencies and bandwidths, representing the distances and communication costs among hardware components. We have implemented HwTopoLB using the Charm++ Parallel Runtime System and evaluated its performance with two different benchmarks and one application. Our experimental results with HwTopoLB exhibit scalability over clustered multi-core compute nodes, and average performance improvements of 23% over execution without load balancers and 19% over the existing load balancing strategies on different multi-core systems.     

Fine grained load balancing in multi-hop wireless networks

In this paper we address the problem of local balancing in multi-hop wireless networks. We introduce the notion of proactive routing: after a short pre-processing phase in which nodes build their routing tables by exchanging messages with neighbors, we require that nodes decide the relay of each message without any further interaction with other nodes. Besides delivering very low communication overhead, proactive routing protocols are robust against some well known active attacks to network routing. In this framework, we develop a proactive routing protocol that is able to balance the local load. Experiments show that our protocol improves network lifetime up to 98% and that it delivers a network that is more robust against attacks that have the goal of getting control over a large part of the network traffic.     

A new algorithm with segment protection and load balancing for single-link failure in multicasting survivable networks

In this paper, we investigate the problem of failure tolerated multicast requests in survivable networks and propose a new heuristic algorithm called segment protection with load balancing (SPLB) to address the single-link failure. In order to obtain better performances, in SPLB first we consider the techniques of cross-sharing and self-sharing to improve the resource utilization ratio, second we propose a segment protection routing algorithm to overcome the trap problem, and third we design a load balancing method to reduce the blocking probability. Compared with conventional algorithm, SPLB performs better performances. Simulation results meet our expectation.     

Disjoint Hamilton cycles in the star graph

In 1987, Akers, Harel and Krishnamurthy proposed the star graph Σ(n) as a new topology for interconnection networks. Hamiltonian properties of these graphs have been investigated by several authors. In this paper, we prove that Σ(n) contains ⌊n/8⌋ pairwise edge-disjoint Hamilton cycles when n is prime, and Ω(n/loglogn) such cycles for arbitrary n.     

Scalable network file systems with load balancing and fault tolerance for web services

Because of the rapid growth of the World Wide Web and the popularization of smart phones, tablets and personal computers, the number of web service users is increasing rapidly. As a result, large web services require additional disk space, and the required disk space increases with the number of web service users. Therefore, it is important to design and implement a powerful network file system for large web service providers. In this paper, we present three design issues for scalable network file systems. We use a variable number of objects within a bucket to decrease internal fragmentation in small files. We also propose a free space and access load-balancing mechanism to balance overall loading on the bucket servers. Finally, we propose a mechanism for caching frequently accessed data to lower the total disk I/O. These proposed mechanisms can effectively improve scalable network file system performance for large web services.     

基于告警相关概率的负载均衡方法

针对在负载均衡中相关告警分配到不同处理节点上的问题,提出一种基于告警相关概率的负载均衡方法。实验结果表明,该方法适合于传输信息关联的场合,具有负载均匀度较高、告警关联平均破坏度低等优点。     

A grid-based dynamic load balancing approach for data-centric storage in wireless sensor networks

In many data-centric storage techniques, each event corresponds to a hashing location by event type. However, most of them fail to deal with storage memory space due to high percentage of the load is assigned to a relatively small portion of the sensor nodes. Hence, these nodes may fail to deal with the storage of the sensor nodes effectively. To solve the problem, we propose a grid-based dynamic load balancing approach for data-centric storage in sensor networks that relies on two schemes: (1) a cover-up scheme to deal with a problem of a storage node whose memory space is depleted. This scheme can adjust the number of storage nodes dynamically; (2) the multi-threshold levels to achieve load balancing in each grid and all nodes get load balancing. Simulations have shown that our scheme can enhance the quality of data and avoid hotspot of the storage while there are a vast number of the events in a sensor network.