Internet-网络解析课件

Internet网络

6/4/2023结构安排1因特网介绍

1.1因特网概述;1.2因特网发展的三个阶段

1.3因特网的组成;1.4计算机网络中的路由选择算法

1.5因特网的路由选择协议2Internet的拓扑特性2.1增长特性;2.2富人俱乐部特性和优先连接特性2.3幂律分布;2.4层次性;2.5异配性;2.6核数;2.7介数3Internet拓扑产生器6/4/20231.1因特网(Internet)概述internet（互联网）是泛指由多个计算机网络互连而成的计算机网络；Internet（因特网）是指当前全球最大的、开放的、由众多网络相互连接而成的特定计算机网络，它采用TCP/IP协议族，且其前身是美国的ARPANET。进入20世纪90年代以后，以因特网为代表的计算机网络得到了飞速的发展。已从最初的教育科研网络逐步发展成为商业网络。6/4/2023(a)(b)网络互联网（网络的网络）结点链路6/4/2023主机因特网6/4/20231.2因特网发展的三个阶段第一阶段是从单个网络ARPANET向互联网发展的过程。1983年TCP/IP协议成为ARPANET上的标准协议。人们把1983年作为因特网的诞生时间。6/4/2023三级结构的因特网第二阶段的特点是建成了三级结构的因特网。三级计算机网络，分为主干网、地区网和校园网（或企业网）。6/4/2023多层次ISP结构的因特网第三阶段的特点是逐渐形成了多层次ISP结构的因特网。出现了因特网服务提供者ISP(InternetServiceProvider)。6/4/2023用户因特网ISP1ISP2因特网服务提供者用户通过ISP上网根据提供服务的覆盖面积大小以及所拥有的IP地址数目的不同，ISP也分成为不同的层次。6/4/2023一级ISP一级ISP第一层

ISP大公司本地

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第二层

ISP6/4/2023因特网的发展情况概况网络数主机数用户数管理机构数198010102

1021001990103105106101

2000105107108102

20051061081091036/4/20231.3因特网的组成从因特网的工作方式上看，可以划分为以下的两大块：(1)边缘部分由所有连接在因特网上的主机组成。这部分是用户直接使用的，用来进行通信（传送数据、音频或视频）和资源共享。(2)核心部分由大量网络和连接这些网络的路由器组成。这部分是为边缘部分提供服务的（提供连通性和交换）。6/4/2023因特网的核心部分因特网的边缘部分主机网络路由器因特网的边缘部分与核心部分6/4/2023因特网的核心部分因特网的核心部分是由许多网络和把它们互连起来的路由器组成，而主机处在因特网的边缘部分。在因特网核心部分的路由器之间一般都用高速链路相连接，而在网络边缘的主机接入到核心部分则通常以相对较低速率的链路相连接。主机的用途是为用户进行信息处理的，并且可以和其他主机通过网络交换信息。路由器的用途则是用来转发分组的，即进行分组交换的。6/4/2023路由器在路由器中的输入和输出端口之间没有直接连线。路由器处理分组的过程是：把收到的分组先放入缓存（暂时存储）；查找转发表，找出到某个目的地址应从哪个端口转发；把分组送到适当的端口转发出去。

6/4/20231.4计算机网络中的路由选择算法根据路由算法是否能随网络的通信量和拓扑自适应地进行调整，路由算法分为：自适应路由算法（静态路由算法）非自适应路由算法（动态路由算法）

a自适应可从时间和空间两方面进行调整。

b自适应路由选择策略是每个结点周期性地从相邻的结点获得网络状态信息，同时也将本结点做出的决定周期性地通知周围的各个结点。以使这些结点不断地根据网络新的状态更新其路由选择决定。6/4/20231.5因特网的路由选择协议因特网采用自适应路由选择协议。并且由于下述两个原因，因特网采用分层次的路由选择协议：（1）因特网的规模特别大。如果让所有的路由器知道所有的网络应该怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使通信链路饱和。（2）许多单位不愿意外界了解自己单位网络的布局细节和本部分所采用的路由选择协议，但同时还希望连接在因特网上。6/4/2023自治系统AS

(AutonomousSystem)自治系统AS的定义：在单一的技术管理下的一组路由器，而这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议用以确定分组在AS之间的路由。现在对自治系统AS的定义是强调下面的事实：尽管一个AS使用了多种内部路由选择协议和度量，但重要的是一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。6/4/2023自治系统AS间采用BGP协议BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS46/4/20232Internet的拓扑特性

针对不同的预测和改善Internet性能的目的，建立合适的Internet拓扑模型是非常重要的。现在，对Internet的研究主要在AS层面和路由器层面。

Internet是一个典型的复杂网络。下面针对AS层面的拓扑结构展开一些讨论。6/4/20232.1增长特性网络的规模在不断的扩大。即网络中随着时间的前进，不断地有新的结点和新的边加入进来。见图1：Internet增长性6/4/20232.2富人俱乐部特性和优先连接特性Internet中少量的结点具有大量的边，这些结点也称为‘富结点’；它们倾向于彼此之间相互连接，构成‘富人俱乐部’

富人俱乐部连通性它表示的是网络中前r个度最大的结点之间，实际存在的边数L与这r个结点之间总的可能存在的边数的比值。如图2：富人俱乐部所示

6/4/2023优先连接特性：即新的结点更倾向于与那些具有较高连接度和很好适应度的‘大’结点相连接。6/4/20232.3幂律分布通过研究AS层面Internet的统计数据,Faloutsos三兄弟指出AS层面Internet拓扑满足以下四种幂律分布:幂律分布1:∝其中是节点v的度,是将网络中节点按度降序排列节点V的秩,R是秩指数常数幂律分布2:∝其中表明度大于d的节点在整个网络中所占的百分比,D是度指数常数.可以推得R=1/D

6/4/2023幂律分布3:∝其中为网络对应的连接矩阵的特征值,i为将特征值按降序排列时的序列号.特征值指数和连接度指数D间存在近似关系幂律分布4:P(h)∝

其中P(h)为距离不超过h的节点对的数目,其中包括自节点对,并对其他节点对计数两次,H是hop指数常数,可以推得其中c=N+2M,N,M和分别为网络节点数,边数和直径.6/4/20232.4层次性Internet由大量的相互连接的AS系统组成,其中每个AS系统可以被看作Stub域或Transit域.Stub域仅承载那些起源于或终止于域内的通信量;stub域通常是LANTransit域没有这种限制,它的目的是有效地相互连接Stub域.Transit域一般是WAN,MAN,被看作是服务供应商.Stub节点连接一个或多个Transit节点,起源于一个stub节点的路径必须横贯那些作为供应商的transit节点.图P533-86/4/20232.5异配性结论:在Internet网中:Internet网上度数高的节点之间连接比较紧密,即存在富人俱乐部现象,但其绝大多数邻居节点的度数很低.见图3：邻居节点的平均度分布研究表明,通过计算前面所讲过的同配性系数r,发现Internet网的r<0,即Internet网是异配网络.6/4/20232.6核数一个图的K-核是指反复去掉度小于或等于K的节点后,所剩余的子图.若一个节点存在于K-核,而在K+1核中被移去,那么此节点的核数为K.例如:包含N个节点的星形网络的中心节点的度数为N-1,核数为0.节点核数的最大值称为图的核数.节点的核数可以表明节点在核中的深度.图4：Internet的节点核数与度数之间的关系：显示了Internet拓扑数据的节点的核数与度数之间的关系.

由图可以看出,当度数较小时,两者之间呈现幂律关系;当节点度数大于100时,核数基本保持不变.6/4/20232.7介数介数衡量了通过网络中该节点的最短路径的数目.图5：Internet的节点的标准化介数与度数之间的关系：显示了三类Internet拓扑数据的节点的介数与度数之间的关系.6/4/2023Internet拓扑产生器随机图产生器结构产生器基于连接度的产生器6/4/2023Inet

拓扑产生器Inet采用PLGR算法与优先附着实现幂律,重视连通性(最小节点覆盖),并根据最大团尺寸和聚类系数做了优化.先后有Inet1,Inet2,Inet3版本.Inet3建模过程:(1)从用户那里获得节点个数N和N个节点中度为1的节点所占的比例k.(2)根据下式计算Internet从1997年11月份的节点个数增长到N所需的月份数t:N=exp(0.0298t+7.9842)(3)定义和:是度为1的节点的集合,为前三个最大度的节点的集合,为除去中节点以外的其他节点.(4)代入t,根据来计算中节点的度分布,其中a,b,c为已知常数.Internet上度为1的节点所占比例基本是在30%左右.根据度-秩指数增长律来计算中节点的度分布,其中p,q为已知常数.6/4/2023(5)在度大于1的节点间构建一个生成树:令G为所要产生的图,初始为空集;不在G中的度大于1的节点i与G中的一个节点j相连的概率为其中为节点i的度,为度的频率.(6)按照步骤(5)中的概率式,将中的kN个节点连接到G中的节点上.(7)从具有最大度的节点开始,连接G中仍剩余的自由度;在进行这些连接时,以步骤(5)中的概率式随机地选取有着自由度的节点.6/4/2023Brite产生器BRITE期望能构建一个具有代表性,包容性和交互性的拓扑产生器.其中,代表性指期望反映Internet实际拓扑的多个方面,如层次性、连接度分布等；包容性指将多个已经存在的产生器的功能融合在一个拓扑产生器当中;交互性指为广泛使用的仿真应用提供更好的接口界面.Brite生成器主要有4步:在平面上放置节点;在节点间建立内部边;为每个拓扑元素设置属性;以一定的形式输出此拓扑结构.具体过程如下:(1)首先将平面分成HS×HS个正方形，每个正方形被进一步分成LS×LS个小的正方形，每个小