一种高效动态LEO卫星网络流量调节路由算法

针对考虑负载均衡的LEO卫星网络路由算法存在控制网络开销偏大、路由更新不及时以及流量调节机制分配不均等问题,提出了一种基于负载均衡的动态LEO卫星网络路由算法DRLB。根据卫星节点路径记录信息以及后向Agent读取策略设计新的路由机制,获得动态卫星拓扑结构;分析前向Agent的分组格式并删除冗余字段,达到减小网络开销目的;根据数据发送时间间隔构造前向Agent选址策略,提高路由更新效率,通过考虑卫星所处纬度流量分配不均问题,改进流量调节因子,获得更好的负载均衡效果。仿真结果表明,与SDRZ-MA算法相比,DRLB算法在减缓星地之间的控制开销、平均端到端时延等方面具有较好的优势。     

LEO卫星网QoS遗传算法路由协议

为了满足多媒体应用的QoS要求,卫星路由协议应该更有效地利用网络资源,提供更好的QoS保障。为此提出了一个基于遗传算法的LEO卫星网络QoS路由协议,称为遗传卫星路由协议（GSRP）。改进了新的操作函数,如适应度函数、终止函数,以及变异率和路由表。仿真结果表明,GSRP能够实现较少CBP和HBP的可靠的点对点时延约束,以及比传统的算法更有效的负载平衡。     

Distributed on-demand routing for LEO satellite systems

Notwithstanding the limited commercial success of the first narrowband low earth orbit (LEO) satellite systems, the interest of the scientific community in this type of systems has been revived on the basis of the current trend toward the migration to all IP-based services. LEO systems can play a pivotal role in providing services to areas where there is no substantial terrestrial infrastructure. Above all, LEO satellite systems can be used as backbone networks to interconnect autonomous systems worldwide. Such an approach provides flexibility in managing the resulting integrated network infrastructure and supporting innovative applications. In this context, routing data from the source all the way to the destination constitutes a daunting challenge. In this paper, a location-assisted on-demand routing (LAOR) protocol is proposed and evaluated. The proposed protocol introduces for the first time in satellite systems the concept of on-demand routing. However, its implementation is tailored to the requirements imposed by the characteristics of the topology of LEO satellite systems. The performance of the LAOR protocol is assessed for different link-cost metrics and compared to the one of centralized routing protocols proposed in the literature so far. Simulation studies further document and confirm the positive characteristics of the proposed protocol.     

多信道无线Mesh网络负载均衡路由算法研究

针对无线网状网的网络容量问题,在多信道无线网状网模型的基础上,利用线性规划公式对无线网状网的路由问题进行描述,在此基础上提出了一个负载均衡的路由算法,在对业务请求的路由跳步数进行约束的前提上,通过减少网络链路上的负载,达到提高网络的吞吐量的目的。仿真结果表明,提出的算法能显著提高网络性能。     

Topological dynamics characterization for LEO satellite networks

The highly topological dynamics characterizes the most fundamental property of satellite networks with respect to terrestrial ones. The manifest feature directs the researches on various aspects of satellite networks, including protocol architecture investigations, routing protocol and reliable transmission control protocol design and enhancement, etc. This paper systematically quantifies the dynamical activities of regular low earth orbit (LEO) satellite network topologies. The number and length of network snapshots are formulated concisely. With this work, it compensates for the simplified topological assumptions in many LEO satellite network related researches. The thorough understanding of this basic feature not only provides for an accurate quantification of network behavior for researchers on satellite network community, but also could act as a guidance for future satellite constellation design and optimization.     

A routing framework for load balancing of bandwidth sensitive traffic in differentiated service networks

The Differentiated Service (DiffServ) network model has been defined as a scalable framework for providing Quality of Service to applications. In this model, traffic is classified into several service classes with different priorities inside queues of IP routers. The premium service class has the highest priority. Due to the high priority of premium traffic, the global network behaviour against this service class, including routing and scheduling of premium packets, may impose significant influences on traffic of other classes. These negative influences, which could degrade the performance of low-priority classes with respect to some important metrics such as the packet loss probability and the packet delay, are often called the inter-class effects. To reduce the inter-class effects, the premium-class routing algorithm must be carefully selected such that (1) it works correctly (i.e., without loop) under the hop-by-hop routing paradigm; and (2) the congestion resulted from the traffic of premium class over the network becomes minimum. In this paper, we first introduce a novel routing framework, named compatible routing, that guarantees loop-freedom in the context of hop-by-hop routing model. Then, upon this framework, we propose two multipath architectures for load balancing of high-priority traffic on DiffServ networks. Our extensive simulations clearly demonstrate that the proposed methods distribute the premium bandwidth requirements more efficiently over the whole network and perform better than the existing algorithms, especially in the case of complex and highly loaded networks.     

Distributed load balancing mechanism for detouring schemes of geographic routing in wireless sensor networks

Well-known ‘routing hole’ problem of geographic routing is hardly avoided in wireless sensor networks because of various actual geographical environments. Existing geographic routing protocols use perimeter routing strategies to find a detour path around the boundary of holes when they encounter the local minimum during greedy forwarding. However, this solution may lead to uneven energy consumption around the holes since it consumes more energy of the boundary sensors. It becomes more serious when holes appear in most of routing paths in a large-scale sensor network. In this paper, we propose a novel distributed strategy to balance the traffic load on the boundary of holes by virtually changing the sizes of these holes. The proposed mechanism dynamically controls holes to expand and shrink circularly without changing the underlying forwarding strategy. Therefore, it can be applied to most of the existing geographic routing protocols which detour around holes. Simulation results show that our strategy can effectively balance the load around holes, thus prolonging the network life of sensor networks when an existing geographic routing protocol is used as the underlying routing protocol.     

基于GEO/LEO卫星通信网的路由策略研究

从优化卫星网络管理的角度,提出了GEO/LEO卫星通信网络体系结构,该结构将管理子网与业务子网在物理上相互分离,体现了与地面网络不同的集中式路由策略的优势,同时利用卫星运行的规律性和星际链路分布的规则性,制定了极大降低运算量的备用路由策略,保证了GEO/LEO卫星网络体系结构的可靠性,通过仿真验证了两种路由策略的性能。     

一种面向低轨卫星网络的高效无证书身份认证方案

针对现有低轨卫星网络认证方案采用集中认证方式存在认证时延大和采用复杂的双线性映射存在计算开销大的问题。引入无证书认证模型,在Gayathri方案的基础上;设计了一种高效无证书认证方案。该方案将用户的公钥和真实身份统一起来,使得认证过程中不需要第三方参与,降低了认证时延;通过椭圆曲线上少量点乘和点加运算构建认证消息,避免使用双线性映射,降低了计算开销;并在随机预言模型下,基于椭圆曲线离散数学对问题假设,对其安全性进行了证明。最后,通过实验仿真,与现有低轨卫星身份认证方案相比,所提方案的认证时延、计算开销和通信开销较低。     

Packet routing algorithm for polar orbit LEO satellite constellation network

The proliferation of Internet motivates the need of integrating IP with Low Earth Orbit (LEO) satellite networks that are well known for their global coverage and their ability of providing services with different QoS specifications. There is no doubt tha…     

A load balancing multi-path routing scheme based on effective voids for optical burst switching networks

Multi-path routing in the optical burst switching(OBS) networks can reduce the burst loss probability(BLP) by distributing the data burst traffic to multiple paths, compared with single path routing. Unlike the other multi-path routing schemes without considering the carrying capability of the routes, a new multi-path routing scheme based on effective voids(MPEV) is proposed to balance the load of multi-path and reduce the BLP in the paper. MPEV scheme first obtains the information on effective voids of the bottleneck link of multipath by sending a probe packet periodically. The effective voids can accommodate data bursts and accurately represent the available channel resource that is the main determinant of the BLP for OBS networks without optical random access memory. Then MPEV scheme distributes the burst traffic between an ingress node and an egress node to multiple link-disjoint paths by the ratio of the effective voids. More traffic is distributed to the path that has more effective voids, and vice versa. And the distributed amount is proportional to the effective voids of the bottleneck link. So MPEV scheme can balance the load of multi-path routes and can effectively reduce the BLP by avoiding the high load of a single path. And it is easy to implement and agilely adapt to dynamic network traffic. The performance of MPEV scheme is analyzed by queuing theory and is evaluated by simulation. The numerical results show that the proposed scheme can effectively reduce the BLP and balance the traffic load over multiple paths at the same time.     

一种用于MEO/LEO卫星网络管理的分簇算法

卫星网络是一种新型的无线网络形式,可以看作是一种特殊的ad hoc网络。但由于其本身具有的特殊性质,现有的无线网络管理协议不能高效地应用于卫星网络中。通过引入ad hoc网络中分簇的概念,提出了一种适用于MEO/LEO卫星网络管理的基于地理信息辅助的分簇算法。簇首及管理员由MEO卫星担任,管理代理设置在LEO卫星之上。LEO卫星轨道所处的外层空间被划分成移动的分区,根据结点的密度分区合并为簇,然后在簇内根据组合加权方式选择一个MEO结点作为簇首。该算法考虑了不同层卫星之间的相对移动性及卫星运动的规律性,明确了管理员及管理代理的设置位置,为卫星网络管理提供了一种有价值的研究方法。     

A load balancing virtual level routing (LBVLR) using mobile mule for large sensor networks

The Journal of Supercomputing - In a large sensor network, the data are usually routed back to the static base station (BS) using multi-hop communication. The sensor nodes near the BS suffer from...     

负载平衡路由：一种新的ACO路由策略*

通过改进ACO算法达到一种能实现通信网络负载平衡的群体智能路由策略。采用的主要方法为：将蚁群划分为若干个子群,不同子群的蚂蚁释放不同类型的信息素。通过不同类型信息素之间的相互制约作用,以及链路负载的测量,提出了三种策略实现负载平衡路由。在模拟网络上进行了不同策略的对比实验,以及与已有的群体智能路由算法的运行测试比较。实验结果表明,本文的路由策略具有较好的效果和一定的优势。     

Replica-aided load balancing in overlay networks

In recent years, there have been rapid advances in network infrastructure and technologies for end-user communication. However, because of network dynamics and resource limitation, providing scalable end-user communication services is challenging when the applications are utilized on a large-scale. To address this challenge, a replica-aided load balancing scheme (RALB) is proposed for enabling the nodes in an overlay networks to support the communication applications for a large number of users. This paper makes three unique contributions. First, we study the existing load balancing schemes and identify their weakness in handling time-varying workloads with frequent load fluctuations. Second, we introduce a sophisticated cost model for load balancing cost estimation, which captures the dependencies between the factors (e.g., the load, message number, and link latency). Third, we propose a performance tuning technique to minimize the load balancing cost. The extensive experiments show that RALB effectively reduces the load imbalance and eliminates the load balancing cost when compared to the existing load balancing schemes.     

Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing

In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191–207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted.     

Reinforcement learning for resource allocation in LEO satellite networks.

In this paper, we develop and assess online decision-making algorithms for call admission and routing for low Earth orbit (LEO) satellite networks. It has been shown in a recent paper that, in a LEO satellite system, a semi-Markov decision process formulation of the call admission and routing problem can achieve better performance in terms of an average revenue function than existing routing methods. However, the conventional dynamic programming (DP) numerical solution becomes prohibited as the problem size increases. In this paper, two solution methods based on reinforcement learning (RL) are proposed in order to circumvent the computational burden of DP. The first method is based on an actor-critic method with temporal-difference (TD) learning. The second method is based on a critic-only method, called optimistic TD learning. The algorithms enhance performance in terms of requirements in storage, computational complexity and computational time, and in terms of an overall long-term average revenue function that penalizes blocked calls. Numerical studies are carried out, and the results obtained show that the RL framework can achieve up to 56% higher average revenue over existing routing methods used in LEO satellite networks with reasonable storage and computational requirements.     

Agent-based load balancing on homogeneous minigrids: macroscopic modeling and characterization

In this paper, we present a macroscopic-characterization of agent-based load balancing in homogeneous minigrid environments. The agent-based load balancing is regarded as agent distribution from a macroscopic point of view. We study two quantities on minigrids: the number and size of teams where agents (tasks) queue. In macroscopic modeling, the load balancing mechanism is characterized using differential equations. We show that the load balancing we concern always converges to a steady state. Furthermore, we show that load balancing with different initial distributions converges to the same steady state gradually. Also, we prove that the steady state becomes an even distribution if and only if agents have complete knowledge about agent teams on minigrids. Utility gains and efficiency are introduced to measure the quality of load balancing. Through numerical simulations, we discuss the utility gains and efficiency of load balancing in different cases and give a series of analysis. In order to maximize the utility gain and the efficiency, we theoretically study the optimization of agents' strategies. Finally, in order to validate our proposed agent- based load balancing mechanism, we develop a computing platform, called simulation system for grid task distribution (SSGTD). Through experimentation, we note that our experimental results in general confirm our theoretical proofs and numerical simulation results from the proposed equation system. In addition, we find a very interesting phenomenon, that is, agent-based load balancing mechanism is topology-independent.     

一种高效的融合负载均衡和路由节能的路由算法

基于SDN(software defined networking)体系结构的迭代式负载均衡与节能的流调度算法(load balancing and energy saving flow scheduling with iteration,LoadbE-it)在实现负载均衡的同时最高可节约25％左右的能耗,但其时间复杂度为O(n4),不利于在大规模网络中部署.LoadbE-it-M算法(load balancing and energy saving flow schedu-ling with iteration multiple)通过逐步减少网络拓扑中需要计算的链路数量来提升运行效率.理论和实验结果表明,LoadbE-it-M算法不仅具有较小的计算开销,并且与LoadbE-it算法具有同样的负载均衡能力和节能效果.     

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.