Distributed routing for load balancing

Some open-loop and closed-loop control algorithms are discussed for an example of a discrete-event system, namely, the routing of arriving tasks from different arrival streams among several possible service stations. It is shown that it is possible to design open-loop policies that give good performance in a way which is very robust with respect to large changes in the arrival rates. This is possible even though it is assumed that there is no online coordination between the routing algorithms for the different arrival streams. Some further improvements of the performance are possible when a simple feedback policy, namely, overflow routing, is implemented. This also gives reasonable robustness of performance with respect to changes in the service rates     

Load balancing routing with queue overflow prediction for WSNs

The ease of deployment of Wireless Sensor Networks (WSNs) makes them very popular and useful for data collection applications. Nodes often use multihop communication to transmit data to a collector node. The next hop selection in order to reach the final destination is done following a routing policy based on a routing metric. The routing metric value is exchanged via control messages. Control messages transmission frequency can reduce the network bandwidth and affect data transmission. Some approaches like trickle algorithm have been proposed to optimize the network control messages transmission. In this paper, we propose a collaborative load balancing algorithm (CoLBA) with a prediction approach to reduce network overhead. CoLBA is a queuing delay based routing protocol that avoids packet queue overflow and uses a prediction approach to optimize control messages transmission. Simulation results on Cooja simulator show that CoLBA outperforms other existing protocols in terms of delivery ratio and queue overflow while maintaining a similar end-to-end delay.

     

Hybrid routing and load balancing protocol for wireless sensor network

In wireless sensor network, when the nodes are mobile, the network structure keeps on changing dynamically, that is, new nodes enter the network and old members exit the network. As a result, the path from one node to the other varies from time to time. In addition, if the load on a particular part of the network is high, then the nodes will not be capable of transmitting the data. Thus, data delivery at the destination will be unsuccessful. Moreover, the part of the network involved in transmitting the data should not be overloaded. To overcome these issues, a hybrid routing protocol and load balancing technique is discussed in this paper for the mobile data collectors in which the path from source to destination is ensured before data transmission. The hybrid routing protocol that combines the reactive and proactive approach is used to enhance gradient based routing protocol for low power and lossy networks. This protocol can efficiently handle the movement of multiple sinks. Finally, load balancing is applied over the multiple mobile elements to balance the load of sensor nodes. Simulation results show that this protocol can increase the packet delivery ratio and residual energy with reduced delay and packet drop.     

Domain load balancing routing for multi-gateway wireless mesh networks

As Wireless Mesh Networks (WMNs) are typically used for Internet access, most traffic is routed through the gateways which connect WMN to the wired network. As a result, the gateways tend to get congested and balancing of the traffic load of gateways is critical. In this paper, we consider applications that require continuous provision of a certain bandwidth to a server located at the wired network. If a path that satisfies the bandwidth request cannot be found, the request will be rejected, so that load imbalance will result underutilization of the network capacity. We present a novel load balancing routing algorithm for maximizing the network utilization (i.e., accommodating service requests as many as possible) for multi-gateway WMNs. In the proposed scheme, a WMN is divided into domains. Each domain is served by one gateway, so that all traffic of a domain is served by the corresponding gateway. Our scheme determines routing to balance the traffic load among domains, and then performs load balancing routing within each domain. Simulation results show that in square grid topologies, our intra-domain routing achieves near optimal performance with about 70% less overhead than the existing schemes. Our inter-domain load balancing scheme outperforms the existing heuristics by up to 25% while achieving about 80% performance of the optimal solution.     

Congestion detection technique for multipath routing and load balancing in WSN

In WSN, nodes collect the information from the surrounding environment and transferring to base station. Multiple data transmission in a WSN causes the nodes near the base station to get congested. Here we propose to develop a congestion avoidance and mitigation technique. For that, we select routes based on the distance between sender and receiver, relative success rate (RSR) value of node and buffer occupancy of a node. Based on these three parameters, we define a utility function to be applied to each neighbor of a transmitter node. Hence the transmitter node chooses the highest U-valued node as its next hop node among its neighbors in packet forwarding. Thus we avoid congestion by choosing non-congested nodes as its next hop node and then we mitigate congestion based on RSR values.     

An adaptive load balancing scheme for web servers

This paper describes an overload control scheme for web servers which integrates admission control and load balancing. The admission control mechanism adaptively determines the client request acceptance rate to meet the web servers' performance requirements while the load balancing or client request distribution mechanism determines the fraction of requests to be assigned to each web server. The scheme requires no prior knowledge of the relative speeds of the web servers, nor the work required to process each incoming request. Copyright © 2002 John Wiley & Sons, Ltd.     

Distributed out-bound load balancing in inter-AS routing by random matchings

The Internet is composed of a collection of inter-connected and self-administered Autonomous Systems (ASms). Inter-AS routing is accomplished by having neighboring ASms exchange reachability information via the Border Gateway Protocol. An AS is said to be a transit AS if it allows traffic from other ASms to cross through it. In particular, transit ASms provide transit services for traffic between customer and provider ASms. In this article, we focus on maximizing the utilization of resources at transit ASms. In particular, inter-AS links have been shown to be a bottleneck. To make better use of inter-AS links, we consider the problem of balancing the load among inter-AS links. We refer to this problem as the Balanced-Flow Assignment ProbleM (B-FAPM). We show that the B-FAPM is NP-hard, and thus, likely intractable. We then present a heuristic protocol, the Balanced-Flow Assignment ProtocoL (B-FAPL), that balances the out-bound traffic loads on inter-AS links. We show via simulation that the B-FAPL effectively balances outgoing traffic over inter-AS links. Our solution is fully distributed and uses random matchings to assign in-bound flows to out-bound inter-AS links. Ravi Musunuri received his Bachelors degree from R. V. College of Engineering, Bangalore, India, in 1998, and his Masters and Ph.D. degrees in the Computer Science Department from the University of Texas at Dallas in 2002 and 2006, respectively. He is currently with Cisco Systems, San Jose. His research interest broadly is in Computer Networks area with emphasis on Internet routing, Wireless Sensor Networks, and Content Delivery Networks. Jorge Arturo Cobb received his B.S. degree in computer science with highest honors from the University of Texas at El Paso in 1987, and M.A. and Ph.D. degrees, both in computer science, from the University of Texas at Austin in 1989 and 1996, respectively. He is currently an associate professor in the Department of Computer Science at the University of Texas at Dallas. His main research interest is in computer networking, with an emphasis on scheduling for quality of service guarantees and mobile computing.     

Distributed potential field based routing and autonomous load balancing for wireless mesh networks

Congested hot spots and node failures severely degrade the performance of wireless mesh networks. However, conventional routing schemes are inefficient in mitigation of the problems. Considering analogy to physics, we propose a novel distributed potential-field-based routing scheme for anycast wireless mesh networks, which is robust to sudden traffic and network perturbations, effectively balancing load among multiple gateways and mesh nodes with little control overhead. Simulation results exhibit autonomous load balancing and failure-tolerant performance in wireless mesh networking.     

Min-max load balancing scheme for mixed multicast and unicast services in LTE networks

To avoid the traffic congestion in long term evolution (LTE) networks,a min-max load balancing (LB) scheme is proposed to minimize the demanded radio resources of the maximum loaded cell.For the mixed ...     

Optimization of link load balancing in multiple spanning tree routing networks

In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a?set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total number of network links), and the second objective is the minimization of the average link load (when n is smaller than the total number of network links). Besides exact methods, a heuristic technique that can compute both feasible solutions and lower bounds for the addressed optimization problem is proposed. Finally, we discuss effectiveness of different solution using results of a numerical study of realistic case studies.     

多域SDN网络中负载均衡路由算法研究

SDN是一种新型的网络架构,可分离数据平面和控制平面。其通常利用集中控制器来管理所有的网络中的交换机。随着网络规模的扩大,单个控制器的有限性能将导致控制平面拥塞,一些方案被提出以解决可扩展性问题,即将网络分离多个域。文章分析了现有的跨域交互技术以及负载均衡算法,并对已有的负载均衡算法作出比较。     

A dynamic routing algorithm with load balancing heuristics for restorable connections in WDM networks

Dynamic routing of a restorable connection requires a pair of link-disjoint primary and backup lightpaths to be found online when a connection request arrives at the network. We present a distributed dynamic routing algorithm for restorable connections that uses load balancing heuristics in both primary and backup path computations to achieve low demand blocking. The key idea is to assign costs to links so that heavily loaded links will be avoided in the routing of the primary and backup paths and links with a high chance of including a sharable backup channel will be included in the backup path. Simulation results showed that the algorithm performs significantly better than a simple distributed algorithm and achieves comparable performance as a centralized algorithm.     

Ant colony optimization based load balancing routing and wavelength assignment for optical satellite networks

An ant colony optimization (ACO) based load balancing routing and wavelength assignment (RWA) algorithm (ALRWA) was put forward for the sake of achieving a fairy load balancing over the entire optical satellite networks. A multi-objective optimization model is established considering the characteristic of global traffic distribution. This not only employs the traffic intensity to modify the light path cost, but also monitors the wavelength utilization of optical inter-satellite links (ISLs). Then an ACO algorithm is utilized to solve this model, leading to finding an optimal light path for every connection request. The optimal light path has the minimum light path cost under satisfying the constraints of wavelength utilization, transmission delay and wavelength-continuity. Simulation results show that ALRWA performs well in blocking probability and realizes efficient load balancing. Meanwhile, the average transmission delay can meet the basic requirement of real-time business transmission.     

基于流量限制的动态自适应路由选择算法

随着网络资源和网络需求的不断同步增长,网络拥塞问题日益突出,如何依据实际网络状况动态选择路由尤为重要.由于应用于TSP问题的蚁群算法具有很强的自适应性和随机性,也被用于解决动态路由问题.文章结合MMAS模型,对AS算法进行了一些改进.同时也综合考虑网络节点间最短距离、流量变化及容量限制等多方面的因素,使用蚁群算法寻找最优路由序列,进行动态路由选择.仿真结果显示,蚁群算法在网络拥塞概率方面明显优于传统算法.     

Supervisory routing control for dynamic load balancing in low data rate wireless sensor networks

Routing protocols for Wireless Sensor Networks (WSN) are designed to select parent nodes so that data packets can reach their destination in a timely and efficient manner. Typically neighboring nodes with strongest connectivity are more selected as parents. This Greedy Routing approach can lead to unbalanced routing loads in the network. Consequently, the network experiences the early death of overloaded nodes causing permanent network partition. Herein, we propose a framework for load balancing of routing in WSN. In-network path tagging is used to monitor network traffic load of nodes. Based on this, nodes are identified as being relatively overloaded, balanced or underloaded. A mitigation algorithm finds suitable new parents for switching from overloaded nodes. The routing engine of the child of the overloaded node is then instructed to switch parent. A key future of the proposed framework is that it is primarily implemented at the Sink and so requires few changes to existing routing protocols. The framework was implemented in TinyOS on TelosB motes and its performance was assessed in a testbed network and in TOSSIM simulation. The algorithm increased the lifetime of the network by 41 % as recorded in the testbed experiment. The Packet Delivery Ratio was also improved from 85.97 to 99.47 %. Finally a comparative study was performed using the proposed framework with various existing routing protocols.     

Multicast routing, load balancing, and wavelength assignment ontree of rings

There are two steps to establish a multicast connection in WDM networks: routing and wavelength assignment. The shortest path tree (SPT) and minimum spanning tree (MST) are the two widely used multicast routing methods. The SPT method minimizes the delay from the source to every destination along a routing tree, and the MST method is often used to minimize the network cost of the tree. Load balancing is an important objective in multicast routing, which minimizes the maximal link load in the system. The objective of wavelength assignment is to minimize the number of wavelengths used in the system. This paper analyzes the performance of the shortest path tree (SPT) and minimum spanning tree (MST) methods in the tree of ring networks, regarding the performance criteria such as the delay and network cost of the generated routing trees, load balancing, and the number of wavelengths required in the system. We prove that SPT and MST methods can not only produce routing trees with low network costs and short delays, but also have good competitive ratios for the load balancing problem (LBP) and wavelength assignment problem (WAP), respectively     

虚拟化网络平台下的负载平衡动态路由选择研究

为解决计算机网络实验室投资成本高与真实环境少的问题,本文拟将GN3网络模拟器引入计算机网络课程的实训教学中,可以生成与真实设备一样的运行环境.以思科路由器的EIGRP配置为例,设计了一个动态路由配置方案拓扑图,并给出详细的配置命令,对实验效果进行了仿真验证与分析.     

A two-stage switch with load balancing scheme maintaining packet sequence

In this letter, we propose a novel load-balancing scheme for two-stage switches, which does not disturb the sequence of packets. The proposed scheme uses chamber queues (CQs) in front of the second crossbar fabric as well as VOQs in front of the first crossbar. While the proposed scheme is very simple, it can achieve 100% throughput under not only uniform but also non-uniform traffic. Moreover, the simulation results show that the average delay of packets in the proposed two-stage switch is lower than that of the original two-stage switch.     

低能耗节点位置未知无线传感器网络控制方案

介绍了一种低能耗节点位置未知的网络控制方案,根据不同的网络运行轮数设定网络节点的通信半径,使网络具有良好的能量有效性.网络中基站经过构建阶段的启动过程、节点信息收集过程和节点信息上报过程,获得了整个网络节点的相对位置分布,然后整合节点-节点信息支路,得到具有回路链接的簇首节点集,其他节点根据自己邻居信息选择簇首节点,实现网络近似最小能耗拓扑的构建.通过仿真与同类典型算法LEACH-C、MCLB进行比较,结果显示该方案应用于网络运行时具有更长的网络生命周期、更少的信息总数和更低的网络构建代价.