针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.     

紧凑路由研究

传统的最短路径路由策略通常需要在每个节点上维护到所有其他节点的路由信息,路由表大小随着网络规模的增加而快速增长,因此可扩展性不好.紧凑路由能够有效降低路由表的增长速度,允许通过路径的小幅拉伸来大幅缩减节点的路由表,从而在路径长度和路由表规模之间获得比最短路径路由更好的平衡.针对通用网络或特定拓扑类型的网络提出了许多紧凑...     

大规模网络上基于图嵌入的可扩展路由方法

大规模网络上理想的路由方法必须同时具有较小的路由表和较短的路径.传统的最短路径路由算法只考虑优化路径,但是路由表需要维护到所有节点的路由信息,故路由表项数至少随网络规模线性增长,因此呈现较差的扩展性.针对基于图嵌入的可扩展路由进行了研究,提出将网络嵌入到由它的支撑图(spanner)导出的度量空间.利用真实网络普遍存在的小世界和无标度拓扑特征,提出了一种嵌入和路由方法--GEROUTE,它用源于高度节点的树形支撑图来构造嵌入,对节点分配较短的标记,使得节点在支撑图上的距离能够由标记推算出来,在节点标记定义的度量空间中使用贪心路由,而节点的路由表只需要存放邻居的标记.分析和仿真表明该路由方法在像Internet的这类图上能够取得比较理想的路由性能,与其他同类方法相比表现更好.     

无标度网络上名字无关的紧凑路由研究

紧凑路由是一类可扩展路由方法,能够在使用较短路径路由的同时,大幅降低节点路由表的空间开销.为解决Internet的路由扩展问题,无标度网络上的紧凑路由最近引起了关注.然而,以往的紧凑路由方法大多是名字有关的,即必须对网络节点重新命名或编址,这对于真实网络是不太实际的.针对无标度网络提出了一种名字无关的紧凑路由方法,即不需要显式改变节点的名字,任何节点只需要知道目的节点的原始名字就可以将包送达,因此具有更好的实用性.该方法在名字有关的紧凑路由方法基础上,引入一种名字映射系统.路由过程一般分为两个阶段:先由目的节点的原始名字查询其隐藏的地址,然后根据该地址路由.为了优化路由的性能指标,选择无标度网络中度最大的部分节点作为路由用的地标,并在这些地标上均匀且分布地为所有节点建立名字到位置的映射.分析和仿真表明,该路由方法可以在无标度网络上取得很高的路由性能,与以往最优的名字无关紧凑路由方法相比,在拉伸系数和路由表大小方面都有显著提高.     

无线传感器网络中保证交付的贪心路由算法

针对传感器网络提出了一种高效的点对点的路由方法.通过对每个节点分配坐标,将网络映射到由它的若干生成树构成的度量空间,根据节点坐标使用贪婪算法路由,即总是选择离目的节点最近的邻居转发包.该方法在每个节点的路由表中只需要维护邻居的坐标,包首部开销最多为O(log2n)2比特.与很多基于位置的贪婪路由算法相比较,该方法的特点是贪婪路由算法能够保证网络中任意一对节点之间都是可达的,并且路径长度不超过这对节点在生成树上的距离.仿真表明该方法同时能够在路径拉伸度和负载平衡上取得较好的性能.     

中心计算的无线传感器网络2-不相交路径路由算法

在多路径路由(multipath routing,MPR)算法中,不相交多路径路由(disjoint multipath routing,DMPR)算法具有更高的可靠性和容错性.DMPR算法面临的主要挑战有2点:不相交路径的选优问题和数据包在不相交路径上的传输问题.针对某些工业应用(例如矿井环境监测)中网络拓扑比较稳定,sink节点运算和存储能力较强等特点,提出了一种中心计算的2-不相交路径路由算法——CCDMPR算法.算法利用全网信息计算出从源节点到sink节点的近似最优2-节点(链路)不相交路径,然后生成仅包含<主父交节点,辅父节点>对和路径比特序列的微路由表并下传到每个节点;针对中心计算方式对链路状态变化的反应迟缓问题,采用了一种中心调度的自适应机制提高路径维护的灵活性.实验结果证明,CCDMPR算法能够显著减小平均路径长度,节省网络整体能量,并能提高数据传输的可靠性.     

基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

基于首选路由的AS 重要性评估方法

准确评估节点的重要性,是增强网络生存性的基础.由于域间路由系统路由策略的复杂性,已有的面向静态拓扑的节点重要性评估方法不能真实反映各个自治系统(autonomous systems,简称AS)在路由中的重要性.首次从动态路由的角度基于AS之间的最优路径从路由上评估各个AS的重要性,经过AS的最优路径数量越多,它就越重要.提出了基于首选路由的AS重要性评估方法,其时间复杂性为O(l×nm),它与面向静态拓扑的评估方法中最好的时间复杂性相同,并且能够更准确地描述节点的实际重要性.通过真实路由数据进行实验,与两种典型的面向静态拓扑的基于顶点度、强度中心性的评估方法对比,其结果表明,基于首选路由的评估方法可以有效发现AS网络中连接较少但很重要的节点,并且评估的重要性与实际的重要性更吻合.     

拓扑隐藏的MANET 安全多路径路由协议

分析了移动自组网(mobile ad hoc network,简称MANET)暴露拓扑带来的安全问题,提出了一种拓扑隐藏的安全多路径路由协议.在路由发现过程中,不在路由包中携带任何路径信息,从而有效隐藏网络拓扑.通过按需的邻居发现进行身份认证并建立路由表项,最终采用排除节点的方法实现多路径的选取;在路由维护过程中,设计了专门的错误发现机制以检验所选路径的有效性和安全性.该协议综合考虑时间因素和路径长度因素,实现了安全的最短路径确定.安全分析表明,该方案可以抵御黑洞攻击、虫洞攻击、rushing攻击和sybil等典型攻击,同时对一般类型的攻击也具有抵御能力.仿真结果表明,与SRP(secure routing protocol)这种典型的安全多路径方案相比,该方案能够找到更多节点不相交的多路径;在普通场景中,该方案没有对协议性能带来额外影响;在黑洞攻击场景中,该方案只需付出一定的信令开销即可大幅度提高数据包转发率,可有效抵御黑洞攻击.     

不规则网络拓扑结构下的多棵树路由算法研究

为了提高不规则网络拓扑结构的路由效率,提出了一种新型路由算法-多棵树路由算法.考虑了原始路由算法的不足,平均了网络中各个通道的利用率,降低路由表的平均路径长度,同时在死锁发生时能够及时有效的进行死锁恢复,解决了先前路由算法中通道负载集中、通道利用率低、路由表平均路径长度过长的问题.通过模拟真实硬件环境的模拟器软件,表明了在不同规模、不同负载下的不规则网络下多棵树路由算法具有更高的效率.     

A novel constant degree and constant congestion DHT scheme for peer-to-peer networks

1 Introduction and related work In recent years, peer-to-peer computing has attracted significant attention from both industry field and academic field[1-3]. The core component of many proposed peer-to- peer systems is the distributed hash table (DHT) schemes[4,5] that use a hash table-like interface to publish and look up data objects. Many proposed DHT schemes[6-15] are based on some traditional interconnection to- pology: Chord[6], Tapestry[7,8], Pastry[9] are based on hypercube topolog…     

基于关键网络状态的域内路由可用性研究

业界通常采用路由保护方案来提高域内路由可用性.然而已有的路由保护方案存在下面两个方面的问题:a)没有考虑网络中链路的失效概率,同等对待网络中所有的链路,事实上在互联网中,不同链路的失效概率是不同的,因此应该在路由保护方案中考虑链路的失效概率;b)将保护链路的数量作为设计目标,事实上方面某些链路出错的概率非常低,保护这些链路反而会增加开销,而另一方面某些链路出错的概率非常高,需要重点保护这些链路.因此应该将路由可用性作为路由保护方案的设计目标.针对上述两个问题,提出了一种基于关键网络状态的域内路由保护方案(RPBCNS),该算法首先通过链路失效概率计算出所有的关键网络状态,然后在每种关键网络状态下计算节点对之间相应的路径,保证节点对之间路径的多样性,从而使得尽可能多的节点对满足路由可用性需求.仿真实验将RPBCNS算法与主流算法ECMP、DC、path splicing分别在三个真实网络中进行对比,在网络可用性和节点对可用性满足率上RPBCNS的性能明显优于其他三种算法.仿真结果表明,RP-BCNS不仅具有较高的网络可用性,并且能够使得尽可能多的节点对满足路由可用性目标,更符合实时应用的实际需求.     

All-to-all disjoint multipath routing using cycle embedding

In this paper, we evaluate the performance of disjoint multipath routing approaches for all-to-all routing in packet-switched networks with respect to packet overhead, path length, and routing table size. We develop a novel approach based on cycle embedding to obtain two node-disjoint paths between all source–destination pairs with reduced number of routing table entries maintained at a node (hence the reduced lookup time), small average path length, and less packet overhead. We study the trade-off between the number of routing table entries maintained at a node and the average length of the two disjoint paths by: (a) formulating the cycle-embedding problem as an integer linear program; and (b) developing a heuristic. We show that the number of routing table entries at a node may be reduced to at most two per destination using cycle-embedding approach if the average length of the disjoint paths are allowed to exceed the minimum by 25%.     

Minimizing hierarchical routing error

In hierarchical routing schemes, nodes are grouped into clusters at multiple levels, and a given node sees only a summarized view of the entire network. Hierarchical routing introduces error, which is the difference between the hierarchical path length and the optimal path length using flat routing. Since in practice the routing table size at each node is limited, we formulate the constrained optimization problems of finding a hierarchy structure that minimizes either the worst case or average case routing error. We prove results characterizing solutions of these problems, and present dynamic programming solution algorithms and computational results.     

Black Hole Attack Detection and Performance Improvement in Mobile Ad-Hoc Network

ABSTRACT

Security is an essential service for mobile network communications. Routing plays an important role in the security of mobile ad-hoc networks (MANETs). A wide variety of attacks targets the weakness of MANETs. By attacking the routing protocols, attackers can absorb network traffic, injecting themselves into the path between the source and destination. The black hole attack is one of the routing attacks where a malicious node advertise itself as having the shortest path to all nodes in the network by sending fake route reply. In this paper, a defense scheme for detecting black hole node is proposed. The detection is based on the timing information and destination sequence numbers maintained in the Neighborhood Route Monitoring Table. The table maintains the record of time of Reply. A black hole node will send a route reply message without checking the routing table as the legitimate node normally does. This reduced reply time is used to detect the black hole node. To improve the security further, the destination sequence number is checked with the threshold value, which is dynamically updated. The simulation results demonstrate that the protocol not only detects black hole attack but also improves the overall performance.     

PGA：一种基于最优路径的Ad Hoc网络地理路由算法

本文提出了一种基于最优路径的Ad Hoc网络的地理路由算法PGA及其改进算法H-PGA,该算法在路径的构造、路由、路由恢复各个方面都应用了最优路径路由的概念,较好地解决了地理路由算法中的凹节点问题.在网络节点数n较大的情况下,依然保持很高的报文投递率(n=400、网络度为4时,报文投递率为96%),且实际路径很接近最短路径路径.同时H-PGA路由表的大小与平方根√n成线性关系,单个节点的协议带宽消耗也为O(平方根n),这使得H-PGA可以适用于较大的应用范围.     

An optimal inherently stabilizing routing algorithm for star P2P overlay networks

Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in an n‐star can be placed in an (n − 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.     

Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．