1、2022年5月30日星期一21时28分37秒Internet 网络 2022年5月30日星期一21时28分37秒结构安排n1 因特网介绍 1.1 因特网概述; 1.2 因特网发展的三个阶段 1.3 因特网的组成; 1.4 计算机网络中的路由选择算法 1.5 因特网的路由选择协议2 Internet 的拓扑特性2.1 增长特性; 2.2 富人俱乐部特性和优先连接 特性2.3 幂律分布; 2.4 层次性; 2.5 异配性; 2.6 核数; 2.7 介数3 Internet拓扑产生器2022年5月30日星期一21时28分37秒1.1 因特网 (Internet)概述ninternet（互联网）是泛指
2、由多个计算机网络互连而成的计算机网络；nInternet（因特网）是指当前全球最大的、开放的、由众多网络相互连接而成的特定计算机网络，它采用TCP/IP协议族，且其前身是美国的ARPANET。n进入 20 世纪 90 年代以后，以因特网为代表的计算机网络得到了飞速的发展。n已从最初的教育科研网络逐步发展成为商业网络。(a)(b)网络互联网（网络的网络）结点链路主机因特网2022年5月30日星期一21时28分39秒1.2 因特网发展的三个阶段n第一阶段是从单个网络 ARPANET 向互联网发展的过程。 n1983 年 TCP/IP 协议成为 ARPANET 上的标准协议。n人们把 1983 年作
3、为因特网的诞生时间。 2022年5月30日星期一21时28分39秒三级结构的因特网 n第二阶段的特点是建成了三级结构的因特网。 n三级计算机网络，分为主干网、地区网和校园网（或企业网）。 2022年5月30日星期一21时28分39秒多层次 ISP 结构的因特网 n第三阶段的特点是逐渐形成了多层次 ISP 结构的因特网。n出现了因特网服务提供者 ISP (Internet Service Provider)。 用户因特网ISP1ISP2因特网服务提供者用户通过 ISP 上网根据提供服务的覆盖面积大小以及所拥有的IP 地址数目的不同，ISP 也分成为不同的层次。 一级 ISP一级 ISP第一层 I
4、SP大公司本地 ISP大公司大公司公司本地 ISP本地 ISP校园网校园网校园网校园网第二层 ISP第二层 ISPNAPNAPAB主机A 本地 ISP 第二层 ISP NAP 第一层 ISP NAP 第二层 ISP 本地 ISP 主机B第一层 ISP第二层 ISP本地 ISP本地 ISP本地 ISP本地 ISP第一层 ISP第一层第二层第三层本地 ISP第二层 ISP本地 ISP本地 ISP本地 ISP本地 ISP第二层 ISP本地 ISP本地 ISP第二层 ISP2022年5月30日星期一21时28分39秒因特网的发展情况概况 网络数 主机数 用户数 管理机构数1980 10 102 102
5、 1001990 103 105 106 101 2000 105 107 108 102 2005 106 108 109 1032022年5月30日星期一21时28分39秒1.3 因特网的组成 从因特网的工作方式上看，可以划分为以下的两大块：(1) 边缘部分 由所有连接在因特网上的主机组成。这部分是用户直接使用的，用来进行通信（传送数据、音频或视频）和资源共享。(2) 核心部分 由大量网络和连接这些网络的路由器组成。这部分是为边缘部分提供服务的（提供连通性和交换）。因特网的核心部分因特网的边缘部分主机网络路由器因特网的边缘部分与核心部分2022年5月30日星期一21时28分40秒因特网的核
6、心部分n因特网的核心部分是由许多网络和把它们互连起来的路由器组成，而主机处在因特网的边缘部分。n在因特网核心部分的路由器之间一般都用高速链路相连接，而在网络边缘的主机接入到核心部分则通常以相对较低速率的链路相连接。n主机的用途是为用户进行信息处理的，并且可以和其他主机通过网络交换信息。路由器的用途则是用来转发分组的，即进行分组交换的。 2022年5月30日星期一21时28分40秒路由器n在路由器中的输入和输出端口之间没有直接连线。n路由器处理分组的过程是：n把收到的分组先放入缓存（暂时存储）；n查找转发表，找出到某个目的地址应从哪个端口转发；n把分组送到适当的端口转发出去。 2022年5月30
7、日星期一21时28分40秒1.4 计算机网络中的路由选择算法n根据路由算法是否能随网络的通信量和拓扑自适应地进行调整，路由算法分为：自适应路由算法（静态路由算法）非自适应路由算法（动态路由算法） a 自适应可从时间和空间两方面进行调整。 b 自适应路由选择策略是每个结点周期性地从相邻的结点获得网络状态信息，同时也将本结点做出的决定周期性地通知周围的各个结点。以使这些结点不断地根据网络新的状态更新其路由选择决定。2022年5月30日星期一21时28分40秒1.5 因特网的路由选择协议n因特网采用自适应路由选择协议。并且由于下述两个原因，因特网采用分层次的路由选择协议：（1）因特网的规模特别大。如
8、果让所有的路由器知道所有的网络应该怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使通信链路饱和。（2）许多单位不愿意外界了解自己单位网络的布局细节和本部分所采用的路由选择协议，但同时还希望连接在因特网上。2022年5月30日星期一21时28分40秒自治系统 AS(Autonomous System) 自治系统 AS 的定义：在单一的技术管理下的一组路由器，而这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由，同时还使用一种 AS 之间的路由选择协议用以确定分组在 AS之间的路由。 现在对自治系统 AS 的定
9、义是强调下面的事实：尽管一个 AS 使用了多种内部路由选择协议和度量，但重要的是一个 AS 对其他 AS 表现出的是一个单一的和一致的路由选择策略。2022年5月30日星期一21时28分40秒自治系统 AS间采用BGP协议BGP 发言人BGP发言人BGP 发言人BGP 发言人BGP发言人AS1AS3AS2AS5AS42022年5月30日星期一21时28分41秒2 Internet 的拓扑特性 针对不同的预测和改善Internet性能的目的，建立合适的Internet拓扑模型是非常重要的。 现在，对Internet的研究主要在AS层面和路由器层面。 Internet是一个典型的复杂网络。下面针对
10、AS层面的拓扑结构展开一些讨论。2022年5月30日星期一21时28分41秒2.1 增长特性n网络的规模在不断的扩大。n即网络中随着时间的前进，不断地有新的结点和新的边加入进来。n见图1：Internet增长性2022年5月30日星期一21时28分41秒2.2 富人俱乐部特性和优先连接特性nInternet中少量的结点具有大量的边，这些结点也称为富结点；它们倾向于彼此之间相互连接，构成富人俱乐部n 富人俱乐部连通性n它表示的是网络中前r个度最大的结点之间，实际存在的边数L与这r个结点之间总的可能存在的边数 的比值。n如图2：富人俱乐部 所示 )/(Nr) 1(22 / ) 1()/(rrLrr
11、LNr2/ ) 1( rr2022年5月30日星期一21时28分41秒n优先连接特性：n 即新的结点更倾向于与那些具有较高连接度和很好适应度的大结点相连接。2022年5月30日星期一21时28分41秒2.3 幂律分布n通过研究AS层面Internet的统计数据,Faloutsos三兄弟指出AS 层面Internet拓扑满足以下四种幂律分布:n幂律分布1: 其中 是节点v的度, 是将网络中节点按度降序排列节点V的秩,R是秩指数常数 幂律分布2: 其中 表明度大于d的节点在整个网络中所占的百分比,D是度指数常数.可以推得R=1/DvdRvr vdvrdDDddD2022年5月30日星期一21时28
12、分41秒n幂律分布3: 其中 为网络 对应的连接矩阵的特征值,i为将特征值按降序排列时的序列号.特征值指数 和连接度指数D间存在近似关系 幂律分布4:P(h) 其中P(h)为距离不超过h的节点对的数目,其中包括自节点对,并对其他节点对计数两次,H是hop指数 常数,可以推得其中c=N+2M, N,M和 分别为网络节点数,边数和直径.iiiiD5 . 0Hh)(hhNhchhPH,)(22022年5月30日星期一21时28分41秒2.4 层次性nInternet由大量的相互连接的AS系统组成,其中每个AS系统可以被看作Stub域或Transit域. Stub域仅承载那些起源于或终止于域内的通信量
13、;stub域通常是LAN Transit域没有这种限制,它的目的是有效地相互连接Stub域.Transit域一般是WAN,MAN,被看作是服务供应商. Stub节点连接一个或多个Transit节点,起源于一个stub节点的路径必须横贯那些作为供应商的transit节点.图P53 3-82022年5月30日星期一21时28分41秒2.5 异配性n结论: 在Internet网中:n Internet网上度数高的节点之间连接比较紧密,即存在富人俱乐部现象,但其绝大多数邻居节点的度数很低.见图3：邻居节点的平均度分布n研究表明,通过计算前面所讲过的同配性系数r,发现Internet网的r0,即Inte
14、rnet网是异配网络.2022年5月30日星期一21时28分41秒2.6 核数n一个图的K-核是指反复去掉度小于或等于K的节点后,所剩余的子图.n若一个节点存在于K-核,而在K+1核中被移去,那么此节点的核数为K.n例如: 包含N个节点的星形网络的中心节点的度数为N-1,核数为0. n节点核数的最大值称为图的核数.节点的核数可以表明节点在核中的深度.n图4：Internet的节点核数与度数之间的关系：显示了Internet拓扑数据的节点的核数与度数之间的关系. 由图可以看出,当度数较小时,两者之间呈现幂律关系;当节点度数大于100时,核数基本保持不变.2022年5月30日星期一21时28分41
15、秒2.7 介数n介数衡量了通过网络中该节点的最短路径的数目.n图5：Internet的节点的标准化介数与度数之间的关系：n显示了三类Internet拓扑数据的节点的介数与度数之间的关系.2022年5月30日星期一21时28分41秒Internet拓扑产生器n随机图产生器n结构产生器n基于连接度的产生器2022年5月30日星期一21时28分41秒Inet 拓扑产生器nInet采用PLGR算法与优先附着实现幂律,重视连通性(最小节点覆盖),并根据最大团尺寸和聚类系数做了优化.先后有Inet1, Inet2, Inet3版本. Inet3建模过程:n(1 )从用户那里获得节点个数N和N个节点中度为1
16、的节点所占的比例k.n(2)根据下式计算Internet从1997年11月份的节点个数增长到N所需的月份数t: N=exp(0.0298t+7.9842)n(3)定义 和 : 是度为1的节点的集合, 为前三个最大度的节点的集合, 为除去 中节点以外的其他节点.n(4)代入t,根据 来计算 中节点的度分布,其中 a,b,c为已知常数.Internet上度为1的节点所占比例基本是在30%左右.根据度-秩指数增长律 来计算 中节点的度分布,其中p,q为已知常数.1V3TOPVV1V3TOPVV1V3TOPVbatcdedF)(diifdF)()(Rqptred3TOPV2022年5月30日星期一21
17、时28分41秒(5)在度大于1的节点间构建一个生成树:令G为所要产生的图,初始为空集;不在G中的度大于1的节点i与G中的一个节点j相连的概率为n其中n 为节点i的度, 为度的频率.(6)按照步骤(5)中的概率式,将 中的kN个节点连接到G中的节点上.(7)从具有最大度的节点开始,连接G中仍剩余的自由度;在进行这些连接时,以步骤(5)中的概率式随机地选取有着自由度的节点.Gkkijiwwji),(jjijijiddfdfddw)()(log)(log, 1max22id)(idf1V2022年5月30日星期一21时28分41秒Brite产生器nBRITE期望能构建一个具有代表性,包容性和交互性的
18、拓扑产生器.其中,代表性指期望反映Internet实际拓扑的多个方面,如层次性、连接度分布等；包容性指将多个已经存在的产生器的功能融合在一个拓扑产生器当中;交互性指为广泛使用的仿真应用提供更好的接口界面.nBrite生成器主要有4步:在平面上放置节点;在节点间建立内部边;为每个拓扑元素设置属性;以一定的形式输出此拓扑结构.具体过程如下:(1)首先将平面分成HSHS个正方形，每个正方形被进一步分成LSLS个小的正方形，每个小的正方形内最多分配一个节点；（2）平面上节点的随机放置：根据一致随机分布或者pareto分布来分布每个正方形内的节点个数；随机选取一个小的正方形，在避免冲突的情况下，将一个节
19、点放入其中。（3）初始产生一个有着 个节点的随机图作为主干，然后添加其他的节点，如果参数IG（incremental growth）为0，则将所有节点一次全部放2022年5月30日星期一21时28分41秒置在平面上，然后然后随机选取一个节点，与其他节点建立m条边；如果IG为1，则每步添加一个节点，将其与网络中的已经存在的节点间建立m条边，m越大拓扑越密。（4）节点间的连接概率的确定：如果参数PC(preferential connectivity）为0，则按其中 ， ，d（u，v）是u和v之间的欧氏距离， 为平均连接度，L是图中相距最远的两节点间的欧氏距离， 决定了边的平均长度。 将所考虑的新节点v与节点i相连;如果PC为1,则v与i相连的概率为BA线性优先连接概率;如果PC为2,则v与i相连的概率为其中 为Waxman概率.Cjjjiiikwkwk)(iwLvudevu/),(),(012022年5月30日星期一21时28分41秒n对于不同的参数IG,PC及不同的节点分布方式,BRITE会产生不同的拓扑特性.实验结果表明,PC=IG=1时,BRITE所产生的拓扑在幂律指数和特征路径长度等方面最接近Internet的实际拓扑.
