拓扑法环境建模最早由谁提出

发布网友发布时间：2022-05-12 01:51

共1个回答

热心网友时间：2023-11-02 13:12

由于目前的网络测量技术无法获得完整而准确的Internet拓扑结构,关于 Internet网络拓扑的建模方法一直都在根据对网络属性的认识程度而变化发展。对Internet网络拓扑建模方法的研究主要经历了三个阶段:最早采用的是随机图模型,仅仅能够根据节点数和节点之间的连接概率构造随机网络,缺乏对Internet实际特征的描述;随后针对Internet网络的结构出现了一些层次模型,这些模型能够根据一定的算法构造几种层次的拓扑结构,但这种层次是定性意义上的,不能对Internet属性进行定量描述;第三阶段是基于Internet幂律分布的建模方法,该方法主要针对Faloutsos等人[1]发现的Internet拓扑结构中存在的幂律特性,能够进一步针对拓扑的定量属性特征进行建模。目前,该类方法仍然是主流的Internet建模方法。本文将根据实际网络在部署过程中遇到的*因素,在保留度分布具有幂律特性的基础上,提出一种更能符合实际Internet路由器级网络的拓扑建模方法。
　　　　1 Internet重要拓扑属性特征分析　　　　由于Internet自身并不存在拓扑测量机制,对Internet网络拓扑发现的研究都是根据一些相关的网络协议功能加以改进而实现的。在当前的研究中,比较公认的Internet属性特征包括以下几点:
　　a)节点度分布符合幂律特性。节点度分布用来表示度为k的节点存在的可能性。在文献[1]于1999年首先发现Internet网络拓扑中节点度符合幂律特性p(k)∝k-r后,该特性已成为当前拓扑建模方法的主要研究对象。
　　b)节点具有明显的层次性。在对Internet自治域级(autonomous system,AS)的网络拓扑研究中发现[2],其拓扑节点之间存在明显的层次性差异。
　　c)聚类系数较高。聚类系数C(k)是一个衡量网络中节点平均度为k的节点与其邻居形成子团容易程度的指标,对于整个网络的聚类系数C就是指所有节点的聚类系数C(k)的平均值。大量研究表明Internet具有较高的聚类系数,文献[3]已采用该特性来衡量拓扑生成算法的正确性。
　　d)相配系数为负值。相配系数是描述节点之间相连是否具有度相关特性的统计量[4]。α0对应同配网络,即网络中节点倾向于与度数相近的节点相连。α<0对应异配网络,表示高度节点倾向于与低度节点建立连接。文献[5]在对BGP、Skitter和WHOIS三个来源的 Internet拓扑数据研究发现,其相配系数分别为-0.19、-0.24和-0.04,这表明Internet拓扑是一个典型的异配网络。
　　e)介数具有幂律特性。介数是一个衡量网络中心度的参数,网络拓扑中节点和边的介数值由任意两点间经过该节点或边的最短路径数来表示。文献[5]在对 Skitter和BGP数据的分析过程中,发现节点的介数与度数关系也存在明显的幂律特性,其幂律指数分别为1.17和1.35。
　　　　2 基于度分布的Internet拓扑模型　　　　对于上述Internet属性特征,目前还没有一个很好的构造算法,使得生成的图符合所有这些特征值。当前基于度分布的拓扑建模方法也主要是对度分布特征进行刻画。其中最著名的是由Barabasi等人[6]首先提出的网络增长—优先连接模型——BA模型。Barabasi等人在研究实际网络中节点和边的变化时发现,Internet是一个增长型网络,节点和边都在不断增加,且边的增加倾向于连接到网络中度数较大的节点上。利用这种增长—优先连接特性,BA模型可以很容易构建具有幂律度分布和小世界特性的网络。
　　BA模型是增长—优先连接算法的最初模型,随后针对Internet中存在大量边的重新连接问题,出现了AB模型[7];针对Internet拓扑的高聚类特征,出现了DM[8]模型;针对Internet中存在的富人俱乐部现象,又出现了正反馈优先(positive feedback preferential,PFP)模型[9]。与此同时,针对Internet中存在大量的叶子节点和节点优先连接的非线性特征,Sagy等人[10] 也提出了TANG模型。TANG模型与PFP模型相类似,都是基于增量加边和非线性优先连接的思想,但TANG模型的非线性因子更加灵活,可以根据需生成拓扑的幂律指数大小进行调节。文献[11]在TANG基于模型的非线性优先连接基础上,根据实际路由器网络的幂律分布特性,提出了一种动态非线性层次(dynamic non-linear hierarchy,DNLH)模型,进一步对路由器网络的幂律特性进行了刻画。
　　　　3 一种路由器级网络拓扑建模方法　　　　上面提到的这些Internet拓扑模型主要是针对网络中节点度分布符合幂律的属性特征,部分考虑了少量其他Internet特征现象,产生的拓扑图无一例外均会出现高度节点互相连接形成网络核心的结构。这是由于在增长—优先连接算法中,核心节点会首先加入到网络中,然后不断与新加入的节点建立连接, 最终使得核心节点具有较高的度值。这种结构在对Internet AS拓扑建模时具有一定的适用性,因为AS拓扑是一个逻辑拓扑,其中的节点和边都不代表实际存在的实体,因而不会有较大*。然而在对Internet路由器级网络进行建模时却存在一个严重的问题,即网络中的节点和边都是由实际网络设备和传输链路构成的,由于受实际网络构造需求、技术实现条件和运行成本的影响,生成的网络拓扑中路由器的连通度受技术实现条件的*不可能很大,两个相距很远的节点之间建立直接链路的概率不可能很高。因而不会像上述模型那样节点的连通度和连接只要满足增长—优先连接规则就可以大量增加。本文将根据实际网络在部署过程中遇到的*,提出一种更能符合实际Internet路由器级网络的拓扑建模方法。
　　在Internet的发展过程中,路由器技术一直对网络连通性的设计产生重要影响。当前不论任何厂家生产的路由器在单位时间内都会存在一个处理数据包的上限,这就*了每台路由器所能具有的最大链路连通数量和最高连通带宽。在一定范围内这两个性能参数还存在一种互相制约的关系,这种制约使得路由器在配置时必须考虑带宽和连通度指标的均衡性。对于网络核心路由器,高带宽是其主要性能指标,因此一般在实际使用时均采用较低的连通度配置方式。同时由于支持高带宽的链路造价昂贵,这种链路仅仅会出现在核心骨干路由器之间和与次一级骨干路由器的连接上。而对于网络边缘路由器,由于其主要工作目的是以为大量终端客户提供服务,而对链路带宽的需求不高,连通性是主要性能指标。以思科路由器为例,图1显示了思科高性能骨干路由器12800系列的工作区域和配置环境。