路由级Internet宏拓扑结构的谱密度分析

针对路由级Internet宏拓扑结构进行了谱密度分布分析与无符号拉普拉斯谱(SLS)分布分析.首先通过对拓扑结构各异的5种采样拓扑图,分别进行谱密度-特征值分布分析,发现5组分析结果表现出高度的一致性,证明了Internet拓扑结构的自相似性,也证明了采样拓扑可以再现局部Internet拓扑结构特征.然后通过采样拓扑图的谱密度-特征值分布函数与ER图、BA无尺度网络拓扑图进行比较,发现三者具有明显区别,得出谱密度-特征值分布函数可作为分辨图谱拓扑结构有效方法的结论.最后通过4组3000点采样拓扑进行SLS分布分析,发现尽管4组3000点采样路由与连接互不相同,但SLS谱分布却非常相似,4组采样拓扑在特征值λ=1处重数均较高,重数次高的特征值都群聚在λ=2处.在特征值从2～103变化过程中表现出较明显的幂律分布特性,其幂指数值保持在3.2813至3.8013之间,特征指数接近.该结论为Internet宏观拓扑结构建模研究提供了量化判据,是Internet拓扑建模研究的重要内容.     

基于属性演化和空间影响的路由级拓扑建模

引入吸引度的概念,对国家级ISP网络拓扑结构进行分析,认为Internet网络拓扑的生长是节点带宽等内在因素与地理位置等外在因素共同作用的结果。综合考虑节点属性的演化及地理空间对网络拓扑的影响,给出一种新的Internet路由级拓扑建模算法,通过实验分析幂律及无符号拉普拉斯谱等度量特征,证明该算法能较真实地模拟Internet路由级拓扑结构。     

面向AS级动态拓扑的改进PFP模型

针对传统PFP模型不能很好模拟Internet动态演化的问题,提出面向自治系统(AS)级动态拓扑的改进PFP模型。改进模型充分考虑Internet中AS节点的消亡与连接边的相应连接补偿,符合Internet拓扑成长和演化过程,生成的Internet拓扑图与实际Internet具有更大相似度。实验结果表明,改进模型能较好满足幂律分布和小世界特性,更适合于Internet建模。     

因特网拓扑结构的幂律分析与建模研究

本文通过对因特网测量拓扑的幂律分布特征,包括frequency-degree幂律分布、degree-rank幂律分布与CCDF(d)-degree幂律分布的研究,发现因特网测量拓扑具有非常明显的frequency-degree幂律分布与degree-rank幂律分布规律。其中,frequency-degree幂律分布符合幂律指数为2.1406的分布规律,而degree-rank幂律分布则分为两部分,主体节点服从幂律指数为0.84639的分布,而度值最大的部分节点却符合幂律指数为0.29981的分布规律。在CCDF(d)-de-gree幂律分布研究中发现,Weibull分布要比幂律分布拟合效果更好。也就是说,对于本文Internet拓扑来说,其节点度的CCDF不一定符合幂律分布。根据frequency-degree幂律幂指数2.1406,本文在BA模型的基础上提出了改进的BA模型,确定网络增长连边概率方程中的ε为0.10812。     

对等网络拓扑测量与特征分析

测量分析对等网络(peer-to-peer networks)拓扑特征是解决P2P优化、网络监管等问题的基础.对等网络是一类大规模、自组织、并且高度动态的复杂网络系统,准确、完整地测量所有对等网络拓扑面临很大困难.研究对等网络的协议特点,分析特定P2P拓扑实例成为认识P2P拓扑特性的一种可选研究方案.以Gnutella网络为测量对象,定义了对等网络拓扑测量系统准确性、完整性的衡量指标,设计、实现了基于正反馈的分布式Gnutella拓扑爬行器——D-Crawler;分析了Gnutella网络拓扑图的度等级分布特征、度频率分布特征以及小世界特性.实验和分析结果表明,对等网络拓扑图属性特征与其使用的协议和客户端软件行为密切相关;Gnutella网络中不同层次的节点之间的拓扑关系表现出不同的特性:上层节点组成的子图具有度等级幂律特征,但在其度频率分布上却呈现出正态分布的特性;下层节点在度等级分布上的幂律特征表现不强烈,而在其度频率分布特征上具有明显的幂律特性.拟合结果表明:幂律能够较好地拟合度等级分布和下层节点度频率分布,然而对于上层节点度概率密度分布,Gaussian拟合效果最好.Gnutella网络具有小世界特性,即:较大的聚集系数和较小的特征路径长度,但它不是无尺度图,不符合BA(Barabási-Albert)生长模型,其发展遵循一种不同于BA模型的生长过程.     

基于节点度分层的路由器级拓扑布局算法

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

AS级Internet拓扑幂律和节点时效分析

Internet拓扑,尤其是AS级拓扑,是目前研究的热点问题.研究Internet拓扑的演化趋势,可以更好地了解网络的内在连接机制.基于CAIDA项目授权的海量数据(数据采集时间为2004年1月至2008年6月),首先介绍了必要的基本概念,然后给出了CCDF(d)-degree幂律分析、degree-rank幂律分析、节点时效分析.结果表明,随着网络拓扑结构的演化,AS级Internet的高度值节点部分较为稳定,保持了网络的聚集性与幂律性,但这部分节点随时间变化逐渐丧失有效连接,网络拓扑呈缓慢均匀化趋势.     

匿名路由器对抽样网络拓扑的影响分析

针对网络拓扑测量中存在的匿名路由器问题,依据Internet网络的主要特征建立一个匿名路由器网络模型,采用类似traceroute的探测机制抽样该网络模型中的路径信息,根据匿名路由器的处理程度分别构造不同的抽样拓扑图,通过研究这些抽样拓扑中的不同属性量化分析匿名路由器问题的影响,其中,拓扑属性包括网络大小、节点度分布、网络路径长度和介数等。     

非广延熵:一种新的Internet拓扑度量

随着Internet规模的不断扩大,Internet拓扑模型已成为网络领域的研究热点。从最初的Waxman随机模型到基于幂律[1]特征提出的BA模型、GLP模型、PFP模型,都试图去发现和解析Internet拓扑演化的规律。节点度、聚簇系数、介数等拓扑度量分别被提出,用于刻画拓扑特征。引入统计物理学上非广延熵[2]作为一个新的拓扑度量,从概率分布的均匀程度上刻画拓扑模型的节点度分布的特征。为了定量地分析非广延熵在不同模型上的差异,通过从CAIDA获得最新的真实拓扑数据,比较BA模型和Waxman模型与真实拓扑数据在非广延熵上是否具有一致性,来验证非广延熵作为拓扑度量的合理性。最后指出BA模型的非广延熵接近真实的Internet拓扑,从而也说明非广延熵作为一种新的拓扑度量的可行性。     

融合多维特征的ISP网络拓扑匹配优化仿真

在复杂多变的网络环境中经常存在拓扑不匹配情况,增加端与端之间的时延以及冗余信息,导致网络整体可拓展性低、传输效率差,提出融合多维特征的ISP网络拓扑匹配优化方法.为更好反映ISP网络覆盖情况与全局匹配程度,构建时间伸缩比、链路匹配度、邻居节点准确率等性能评价指标;分析谱密度、无符号拉普拉斯谱与规格化拉普拉斯谱等多维特性,在特征融合基础上确定新节点,结合新入节点连接策略,建立连接后的成本、时延以及网络健壮性等归一化属性,实现新节点加入,通过节点退出与失效等过程达到拓扑匹配优化目的.仿真结果表明,所提方法网络拓扑值较高,具有良好匹配性,且减少网络开销,符合对网络节点高效率、高灵敏度的要求.     

Modeling generation of the router-level topology of an ISP network

Characterizing the Internet’s router-level topology is important in understanding Internet architecture and how it is linked with technical, economic, and social factors. Hosts on the Internet are connected via thousands of Internet service providers (ISPs), wherein each ISP contains one or more autonomous systems (ASs) depending on its size. An AS is a set of routers within a single administration domain. A major challenge in modeling router-level topology is identifying the factors influencing topological evolution. The current work proposes a router-level topology model in which each router is viewed as resource and attributes, and each link is considered an interaction relationship. We present the concept of “attraction degree” by analyzing the topological data of an actual ISP. We attribute the evolution of the Internet’s router-level topology to interactions among the internal and external factors. In this paper, we also consider the impact of both attribute evolution and geographical limit on topological growth. Using power-law, Laplacian eigenvalue, and heat kernel trace, the proposed modeling algorithm is expected to improve the understanding of researchers and engineers regarding the current Internet situation and how Internet topology will change in the future.     

基于TraceNET的多源协作的拓扑测量方法及其应用

面对日趋复杂的网络,网络的管理变得越来越重要,而网络的故障管理、配置管理、性能管理等都离不开网络拓扑。因此如何高效准确地获得网络拓扑,一直是网络拓扑研究中的一个热点和难点。鉴于此,提出了基于TraceNET的多源协作的拓扑测量方法,并且将该方法用于中国科学技术大学（USTC）校园网拓扑测量,结果表明该方法可以高效准确地绑定路由器的别名和发现子网,因此所提方法具有较高的应用价值。基于USTC校园网上高效准确的测量结果,将此测量方法用于中国教育科研网（CERNET）拓扑测量,可以获得的路由器级拓扑为管理和研究Internet提供了较大价值的参考。     

一种基于复杂网络特性的Internet拓扑模型

文章从复杂网络研究的角度出发,根据Internet的统计特征及其形成机制提出了一种基于消息传递的自组织Internet拓扑模型。该拓扑模型动态模拟整个Internet的生长过程:平面上随机分布的孤立节点通过相互发送消息,消息中保存消息源的优先度等信息,每个节点根据接收到的消息决定如何建立连接。网络由初始的孤立节点自下而上自组织形成一个具有层次结构的Internet拓扑结构。仿真试验表明由该模型生成的拓扑结构在度分布以及聚集系数等方面能够准确地吻合现实Internet拓扑结构。     

Techniques for Determining the Geographic Location of IP Addresses in ISP Topology Measurement

A brief survey on the state-of-the-art research of determining geographic location of IP addresses is presented. The problem of determining the geographic location of routers in Internet Service Provider （ISP） topology measurement is discussed when there is inadequate information such as domain names that could be used. Nine empirical inference rules are provided, and they are respectively （1） rule of mutual inference, （2） rule of locality, （3） rule of ping-pong assignment, （4） rule of bounding from both sides, （5） rule of preferential exit deny, （6） rule of uureachable/timeout, （7） rule of relay hop assignment, （8） rule of following majority, and （9） rule of validity checking based on interface-finding. In totally 2,563 discovered router interfaces of a national ISP topology, only 6.4% of them can be located by their corresponding domain names. In contrast, after exercising these nine empirical inference rules, 38% of them have been located. Two methods have mainly been employed to evaluate the effectiveness of these inference rules. One is to compare the measured topology graph with the graph published by the corresponding ISP. The other is to contact the administrator of the corresponding ISP for the verification of IP address locations of some key routers. The conformity between the locations inferred by the rules and those determined by domain names as well as those determined by whois information is also examined. Experimental results show that these empirical inference rules play an important role in determining the geographic location of routers in ISP topology measurement.     

网络拓扑发现中的路由器别名识别技术研究与实现

网络拓扑发现技术的关键问题之一就是研究路由器之间的连接关系。路由器别名问题是网络拓扑发现技术研究中的一个重要问题,它是指路由器具有多个不同的接口地址,在Internet上可以使用其中的任一地址来标识同一路由器。该文详细描述了路由器别名问题,及其对网络拓扑发现结果带来的影响;重点分析了RFC1122标准中有关路由器的通信规范,描述了别名探子方法的实现原理,并给出了不同应用条件下该方法的实现流程。试验发现,别名探子扫描结果的完整性与目标网络和其他网络连接关系的复杂性有很大关系。分析表明,别名探子方法还存在着种种局限,但在实际应用中,该方法仍不失为一种有效的方法。     

The 2D digraph-based NoCs: attractive alternatives to?the 2D mesh NoCs

This paper proposes two-dimensional directed graphs (or digraphs for short) as a promising alternative to the popular 2D mesh topology for networks-on-chip (NoCs). Mesh is the most popular topology for the NoCs, mainly due to its suitability for on-chip implementation and low cost. However, the fact that a digraph offers a lower diameter than its equivalent linear array of equal cost motivated us to evaluate digraphs as the underlying topology of NoCs. This paper introduces a family of NoC topologies based on three well-known digraphs, namely de Bruijn, shuffle-exchange, and Kautz. We study topological properties of the proposed topologies. We show that the proposed digraph-based topologies have several attractive features including constant node degree, low diameter and cost, and low zero load latency which result in superior performance over the mesh. We introduce a deadlock-free routing algorithm for the proposed NoC topologies and compare NoCs employing the proposed topologies and the mesh topology in terms of power consumption and performance. Simulation results also reveal that the proposed NoC topologies offer higher performance and consume lower power than the mesh NoC.