首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 154 毫秒
1.
一种计算因特网AS拓扑的最短路径的快速算法   总被引:2,自引:1,他引:1  
最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.  相似文献   

2.
为了深入理解和认清Internet AS拓扑中节点度的分配规律,提出适合Internet AS拓扑的幂律模型,利用该模型推导Internet AS拓扑中最富有节点数占网络总节点数的比例与这些最富有节点所拥有的节点度数占网络节点总度数的比例之间的关系,分析研究幂律指数和最大节点度等拓扑参数对该比例关系的影响,通过数值分析发现Internet AS拓扑中27%的最富有节点拥有约73%的节点度数(简称为“73/27”规律),基于Internet AS拓扑经验数据对上述结果进行验证分析,结果表明该幂律模型对Internet AS拓扑是有效的,Internet AS拓扑存在“73/27”规律。  相似文献   

3.
由于真实网络中"富人俱乐部(Rich-Club)"现象的存在,网络中的核心层节点之间的连接度远远高于其它层的节点连接度,且核心层的度分布近似随机分布。文中分析和考察了AS层Internet网络常见的幂率模型,这些模型都能抓住Internet网络幂率分布的特征,但在Rich-Club现象方面存在不足。因此,在BBV模型的基础上提出了改进的幂率拓扑生成算法RBBV。RBBV模型考虑AS层Internet网络Rich-Club现象,并能够恰当地反映网络QoS属性要求。最后,用连续介质理论对RBBV模型进行理论分析,结果表明该模型的点强度和度分布都符合复杂网络的幂率特征。  相似文献   

4.
IP级拓扑是Internet拓扑的细粒度表示,AS级拓扑是Internet拓扑的粗粒度化表示,是Internet宏观结构的抽象。从IP级拓扑及AS级拓扑粗细粒度两个层面来对互联网新生节点的连接偏好及连接稳定性进行探索,验证是否存在BA网络的优先连接的偏好。  相似文献   

5.
覆盖网络技术是下一代互联网、云计算数据中心网、软件定义网络(Software-Defined Network, SDN)等研究领域的热门技术。基于网络测量的覆盖网络可基于实时网络状态数据构建,较好地适应网络的动态性。但该类方法也面临着网络状态信息不完全可测(Incompletely Measurable)的问题,即节点加入所需的全局信息难以测量或在有限的时间内难以获取足够的节点信息,导致部分节点间的网络状态信息缺失,无法顺利完成节点加入过程。为解决该问题,本文提出一种用于不完全可测网络环境的覆盖网络拓扑构造方法(Topology Construction method for Incompletely Measurable network, TCIM),基于时延构建树形拓扑结构。TCIM包含一种高精度节点加入方法和一种低复杂度节点加入方法,其中高精度节点加入算法利用时延三角形的三边关系,为节点选择合适的父节点,用于小规模或静态/低动态性条件下的节点加入;低复杂度节点加入方法在已加入的节点中,自适应选择常数个节点进行测量,选择时延最小的节点作为父节点,可用于大规模、高动态以及网络不完全可测条件下节点的加入。仿真结果表明,TCIM生成的树结构在不同的网络拓扑模型下时延伸缩比(Latency Stretch)均小于对比方法,在Waxman模型和BA模型下取得更小的拓扑维护代价,可通过合理设置TCIM中高精度节点加入和低复杂度节点加入数目构建树形覆盖网络,满足不同的拓扑维护代价和拓扑结构匹配准确度需求。  相似文献   

6.
针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法(DCGN)。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算  相似文献   

7.
面向互联网AS级拓扑监测应用,提出了一种基于最短路径树SPT覆盖的算法,用于选择部署最少的监测点,发现尽量完整的AS拓扑。该算法求出所有顶点的最短路径树,按照启发式策略选择最小的顶点集合,使集合中节点的最短路径树可以覆盖全图的边。采用CAIDA AS -links的数据对算法进行验证,SPT算法选择了750个左右的监测点,即可发现互联网中16 500多个AS之间(约30 000条左右)的链路。与随机选择节点进行覆盖的方法相比,该方法选择的监测点数目减少了近37.5%。  相似文献   

8.
PLDA:AS级的Internet拓扑生成算法   总被引:1,自引:1,他引:0       下载免费PDF全文
朱志伯  高飞 《计算机工程》2010,36(7):115-118
Internet拓扑建模是进行Internet研究的基础。PLOD是一种AS级的Internet拓扑生成算法,但PLOD算法不能保证生成拓扑图的连通性,且存在“出度贷款过剩”现象。对PLOD算法进行改进,提出PLDA算法。在AS节点连接时添加连通性检测,并对出度大的AS节点实行优先连接,较好地解决PLOD算法存在的问题。实验结果表明,PLDA算法是有效可行的。  相似文献   

9.
在对Internet路由器级拓扑的可视化过程中,由于探测结果中节点数量众多和链路复杂,导致布局效果呈现主次不分、边交叉和布局效率低等问题。如何在保证全面展示拓扑中数据和提高布局效率的前提下呈现良好的布局效果是文中的研究重点。针对现有的布局算法都存在布局效果不佳和效率低等问题,提出一种改进的FR算法—DHL( Degree Hier-archical Layout)算法。首先,根据Internet路由器级拓扑中节点度分布的幂律性质将节点分为三类;接着对分类后的节点进行分层显示;最后根据层次的不同选取合理的初始温度和迭代次数。实验结果表明,文中算法能有效降低时间复杂度和边的交叉数,并使布局效果体现网络的层次性。  相似文献   

10.
基于凸片段分解的多边形窗口线裁剪算法   总被引:1,自引:0,他引:1  
将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段.在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作.文中算法能有效地降低裁剪计算的时间复杂度,使其在O(logN)~O(N)之间自适应地变化,且大部分情况下时间复杂度小于O(N).  相似文献   

11.
复杂社会网络的介数性质近似计算方法研究   总被引:4,自引:0,他引:4       下载免费PDF全文
随着计算机和互联网的迅猛发展,面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大,这对网络分析算法的性能提出了更高的要求 。介数值作为图的重要结构性质,广泛应用于基于图的聚类、分类算法,如何降低其计算的复杂性是急需解决的问题。目前,常用的方法是利用对最短路径长度的近似来降低低网络分析算法的复杂性,但已有的近似方法没有考虑现实大规模网络的复杂网络特性,对最短路径长度的近似方 近似计算方法,其基本思想是结合复杂网络的结构特性,利用通过网络中枢节点的路径来近似最短路径,以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算算提供了一种新颖的思路。通过与传统的介数计算方法和近的分析得到了若干有益的结论,为进一步的研究工作奠定了基础。  相似文献   

12.
钱珺  王朝坤  郭高扬 《软件学报》2018,29(3):853-868
随着互联网技术的迅猛发展,社会网络呈现出爆炸增长的趋势,传统的静态网络分析方法越来越难以达到令人满意的效果,于是对网络进行动态分析就成为社会网数据管理领域的一个研究热点。节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力,有利于挖掘社会网络中的重要节点。在图结构频繁变化的场合,若每次变化后都重新计算整个图中所有节点的介数中心度,则效率将会很低。针对动态网络中节点介数中心度计算困难的问题,本文提出一种基于社区的节点介数中心度更新算法。通过维护社区与社区、社区与节点的最短距离集合,快速过滤掉那些在网络动态更新中不受影响的点对,从而大大提高节点介数中心度的更新效率。真实数据集和合成数据集上的实验结果表明了论文所提算法的有效性。  相似文献   

13.
QoS based multicast routing algorithms for real time applications   总被引:1,自引:0,他引:1  
In recent years, there has been a lot of interest in providing real-time multimedia services like digital audio and video over packet-switched networks such as Internet and ATM. These services require certain quality of service (QoS) from the network. The routing algorithm should take QoS factor for an application into account while selecting the most suitable route for the application. In this paper, we introduce a new routing metric and use it with two different heuristics to compute the multicast tree for guaranteed QoS applications that need firm end-to-end delay bound. We then compare the performance of our algorithms with the other proposed QoS-based routing algorithms. Simulations were run over a number of random networks to measure the performance of different algorithms. We studied routing algorithms along with resource reservation and admission control to measure the call throughput over a number of random networks. Simulation results show that our algorithms give a much better performance in terms of call throughput over other proposed schemes.  相似文献   

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

15.
已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法(intra-domain routing protection algorithm based on node diversity,RPBND)。计算节点构造以目的为根的最短路径树(shortest path tree,SPT),从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图(directed acyclic graph,DAG),从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。  相似文献   

16.
Modeling the properties of the Internet topology aims at generating large scale artificial IP networks that mimic properties of real ones for simulation purposes. Current models typically consider the Internet as a simple graph where edges are point-to-point connections between routers. This approach does not take into account point-to-multipoint connections that exist at lower layers in the network, e.g. layer-2 clouds, such as Ethernet switches or MPLS networks. Instead, such physical point-to-multipoint connections are modeled as several logical IP level point-to-point connections.  相似文献   

17.
The WK-recursive networks own two structural advantages: expansibility and equal degree. A network is expansible if no changes to node configuration and link connection are necessary when it is expanded, and of equal degree if its nodes have the same degree no matter what the size is. However, the number of nodes contained in a WK-recursive network is restricted to dt, where d>1 is the size of the basic building block and t⩾1 is the level of expansion. The incomplete WK-recursive networks, which were proposed to relieve this restriction, are allowed to contain an arbitrary number of basic building blocks, while presenting the advantages of the WK-recursive networks. Designing shortest-path routing algorithms for incomplete networks is in general more difficult than for complete networks. The reason is that most incomplete networks lack a unified representation. One of the contributions of this paper is to demonstrate a useful representation, i.e., the multistage graph representation, for the incomplete WK-recursive networks. On the basis of it, a shortest-path routing algorithm is then proposed. With O(d·t) time preprocessing, this algorithm takes O(t) time for each intermediate node to determine the next node along the shortest path  相似文献   

18.
《Computer Communications》2007,30(14-15):2976-2986
A new class of wireless sensor networks that harvest power from the environment is emerging because of its intrinsic capability of providing unbounded lifetime. While a lot of research has been focused on energy-aware routing schemes tailored to battery-operated networks, the problem of optimal routing for energy harvesting wireless sensor networks (EH-WSNs) has never been explored. The objective of routing optimization in this context is not extending network lifetime, but maximizing the workload that can be autonomously sustained by the network.In this work we present a methodology for assessing the energy efficiency of routing algorithms for networks whose nodes drain power from the environment. We first introduce the energetic sustainability problem, then we define the maximum energetically sustainable workload (MESW) as the objective function to be used to drive the optimization of routing algorithms for EH-WSNs.We propose a methodology that makes use of graph algorithms and network simulations for evaluating the MESW starting from a network topology, a routing algorithm and a distribution of the environmental power available at each node. We present a tool flow implementing the proposed methodology and we show comparative results achieved on several routing algorithms.Experimental results highlight that routing strategies that do not take into account environmental power do not provide optimal results in terms of workload sustainability. Using optimal routing algorithms may lead to sizeable enhancements of the maximum sustainable workload. Moreover, optimality strongly depends on environmental power configurations. Since environmental power sources change over time, our results prompt for a new class of routing algorithms for EH-WSNs that are able to dynamically adapt to time-varying environmental conditions.  相似文献   

19.
Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号