《INT计算机网络》PPT课件.ppt

计算机网络,图们因特,计算机网络,1、定义以相互共享资源（硬件、软件和数据）为目的，通过通信链路连接起来，且各自具有独立功能的计算机系统之集合计算机网络通常由三部分组成:资源子网、通信子网和通信协议用作通信链路的介质主要有：双绞线、同轴电缆、光缆、微波和通信卫星等根据计算机网络覆盖的范围可分为局域网、城域网、广域网等,2、网络连接设备,网络连接设备包括：网络接口卡（NetworkInterfaceCard,NIC）中继器(Repeater)，主要用来连接网段，其作用是对信号进行整形，使得信号不至于因为电路衰减而出错调制解调器(Modem)，用于数字信号和模拟信号的相互转换集线器(HUB)，一种特殊的中继，用于网络电缆的中间转接交换器(Switch)是用来连接多网段和中等规模优势的局域网的一种网络连接设备,网络接口卡NIC,网卡起到物理接口作用，计算机通过网卡接入局域网。网卡的ROM上固化有控制通信软件，可实现如下功能：控制数据传送的功能。一方面负责接收网络上的数据包，解包后将数据传输给本地计算机；另一方面将本地计算机上的数据打包后送入网络。串并转换功能。由于计算机内部的数据是并行数据，而一般在网上传输的是串行比特流信息。为防止数据在传输中出现丢失的情况，在网卡上还需要有数据缓冲器，以实现不同设备间的缓冲。网卡上一般有微处理器、控制设备、编码电路、解码电路、ROM、RAM以及手工开关等，这些开关和跳线用来设定各种接口参数的配置，例如对网卡硬件中断级的设置和I/O地址的设置等。网卡的接口类型有三种不同的接头：粗缆AUI接头、细缆BNC接头和双绞线RJ45接头。按照网卡的工作速度它又可分为10Mb/s、100Mb/s、10/100Mb/s自适应和1000Mb/s几种网卡,Ethernet实现方法,Ethernet网卡结构,Ethernet物理地址(MAC地址格式),Ethernet地址=ManufactureID+NICID公司：Cisco00-00-0cNovell00-00-1B00-00-D83Com00-20-AF00-60-8CIBM08-00-5A典型的Ethernet地址：00-60-8C-01-28-12000000001010000010001100000000010010100000010010Ethernet地址具有惟一性，取决于你所使用的网卡。,集线器,又称HUB，是一种特殊的中继器。中继的主要作用是对接收到的信号进行再生放大，以扩大网络的传输距离。集线器是把来自不同的计算机网络设备的电缆集中配置于一体，它是多个网络电缆的中间转接设备，是对网络进行集中管理的主要设备。集线器能自动指示有故障的工作站，并切除其与网络的通信，有利于故障的检测和提高网络的可靠性。集线器的工作方式是从一个端口接收到数据信号后，将该信号放大，转发到其他所有处于工作状态的端口，每一个端口相连的计算机都能收到数据，但仅有与目的地址相符的工作站才接收该数据。集线器某个端口一旦被选中，该端口完全独占全部带宽并与集线器某端口的连接设备进行通信。这时与其它端口相连的计算机即使有信息要传输也必须要等待,集线器的分类独立式HUB这是最早使用于局域网络的集线器,它具有价格低、容易查找故障等特点，适于小型网络，一般支持8-24个工作站。叠加式HUB多个集线器通过一条高速链路叠加起来，它仅支持一种局域网标准（如以太网络，或令牌环网络），不能同时支持多种局域网。这类集线器一般都有少量的容错能力和网络管理功能，可以方便地实现网络的扩充。智能模块化集线器这种集线器采用模块化结构，由机柜、电源、主干面板、插卡和管理模块等组成。它利用高速主干线连起来，可插入Ethernet、Tokenring、FDDI或ATM模块，另外还有网管模块、路由模块等。它一般用于大型网络的主干集线器。这类智能模块化集线器与交换机之间的差别现在越来越小。,单一集线器结构,多集线器级联结构,堆叠式集线器结构,3、网络的拓扑结构,局域网中的不同连接方式构成了网络拓扑结构（Topology）网络拓扑既与节点间的物理连接有关，又关系到节点间进行通信的方式和处理冲突的方式星型总线型环型此外，还有其它一些类型的拓扑结构，如树型、混合型等,CommonLANTopologiesStar（星型结构）网络有一个中央节点，它与所有其它节点直接相连,优点：由于每个设备都用一根线路和中心结点相连，如果这根线路损坏，或与之相连的工作站出现故障时，不会对整个网络造成大的影响，而仅会影响该工作站；网络的扩展容易；控制和诊断方便；访问协议简单；缺点：过分依赖中心结点；成本高,CommonLANTopologiesRing（环型结构）网络中所有的节点用公共传输电缆组成一个闭环，用令牌传递的方法进行访问,优点：路由选择控制简单。信息流沿着固定的一个方向流动，两个站点仅有一条通路；电缆长度短；适用于光纤。光纤传输速度高，而环型拓扑是单方向传输，适用于光纤介质。缺点：结点故障引起整个网络瘫痪。诊断故障困难。具体确定哪一个结点出现故障非常困难，需要对每个结点进行检测。,CommonLANTopologiesBus（总线型结构）网络中所有的节点和工作站都连在一条公共的电缆线上,发送报文的传送方向总是从发送站点开始向两端扩散，在总线网络上的每个站点都会把自己的地址与这个报文的目的地址相比较,只有与该报文目的地址相同的工作站才会接收报文。总线型拓扑结构的介质访问控制方式是叫CSMA/CD（载波监听多路访问/冲突检测）。拓扑结构可靠性高。易于扩充，增加新的站点容易。故障隔离困难。如站点发生故障，需将该站点从总线上拆除，如介质故障，则这段总线要切断。,图1-9树状结构网络,图1-10树状拓扑结构,网状拓扑结构,CERNET主干网拓扑结构,广域网的硬件组成,计算机网络的性能指标,1.速率比特（bit）是计算机中数据量的单位，也是信息论中使用的信息量的单位。Bit来源于binarydigit，意思是一个“二进制数字”，因此一个比特就是二进制数字中的一个1或0。速率即数据率(datarate)或比特率(bitrate)是计算机网络中最重要的一个性能指标。速率的单位是b/s，或kb/s,Mb/s,Gb/s，Tb/s等速率往往是指额定速率或标称速率。,2.带宽“带宽”(bandwidth)本来是指信号具有的频带宽度，单位是赫（或千赫、兆赫、吉赫等）。现在“带宽”是数字信道所能传送的“最高数据率”的同义语，单位是“比特每秒”，或b/s(bit/s)。,常用的带宽单位是千比每秒，即kb/s（103b/s）兆比每秒，即Mb/s（106b/s）吉比每秒，即Gb/s（109b/s）太比每秒，即Tb/s（1012b/s）在计算机界K=210=1024M=220G=230T=240。,3.吞吐量吞吐量(throughput)表示在单位时间内通过某个网络（或信道、接口）的数据量。吞吐量更经常地用于对现实世界中的网络的一种测量，以便知道实际上到底有多少数据量能够通过网络。吞吐量受网络的带宽或网络的额定速率的限制。,4.时延(delay或latency)传输时延（发送时延）发送数据时，数据块从结点进入到传输媒体所需要的时间。也就是从发送数据帧的第一个比特算起，到该帧的最后一个比特发送完毕所需的时间。,传播时延电磁波在信道中需要传播一定的距离而花费的时间。信号传输速率（即发送速率）和信号在信道上的传播速率是完全不同的概念。,处理时延交换结点为存储转发而进行一些必要的处理所花费的时间。排队时延结点缓存队列中分组排队所经历的时延。排队时延的长短往往取决于网络中当时的通信量。数据经历的总时延就是发送时延、传播时延、处理时延和排队时延之和：,总时延=发送时延+传播时延+处理时延+处理时延,四种时延所产生的地方,1011001,发送器,队列,结点B,结点A,在结点A中产生处理时延和排队时延,数据,从结点A向结点B发送数据,链路,（传播）时延,链路,带宽,时延带宽积=传播时延带宽,5.时延带宽积链路的时延带宽积又称为以比特为单位的链路长度。,6.利用率信道利用率指出某信道有百分之几的时间是被利用的（有数据通过）。完全空闲的信道的利用率是零。网络利用率则是全网络的信道利用率的加权平均值。信道利用率并非越高越好。,时延与网络利用率的关系,根据排队论的理论，当某信道的利用率增大时，该信道引起的时延也就迅速增加。若令D0表示网络空闲时的时延，D表示网络当前的时延，则在适当的假定条件下，可以用下面的简单公式表示D和D0之间的关系：,U是网络的利用率，数值在0到1之间。,时延D,利用率U,1,0,D0,时延急剧增大,计算机网络的非性能特征,费用质量标准化可靠性可扩展性和可升级性易于管理和维护,计算机网络体系结构,计算机网络是由多种计算机和各类终端通过通信线路连接起来的复合系统。由于计算机型号不一，终端类型各异，加之线路类型、连接方式、同步方式、通信方式的不同，在不同计算机系统之间，真正以协同方式进行通信的任务是十分复杂的。为了分析设计这样复杂的计算机网络，人们提出了分层的方法。“分层”可将庞大而复杂的问题，转化为若干较小的易于研究和处理的局部问题,1974年，美国的IBM公司宣布了它研制的系统网络体系结构SNA（SystemNetworkArchitecture）为了使不同体系结构的计算机网络都能互连，国际标准化组织（ISO）于1977年成立了一个专门的机构（TC97-SC16）来研究该问题并提出一个标准框架，即开放系统互连参考模型OSI（OpenSystemsInterconnectionReferenceModel）1984年SC16解散，由SC6和SC21进行研究,OSI将整个网络的通信功能划分成七个层次，每个层次完成不同的功能。各层之间是独立的。某一层并不需要知道其它层是如何实现的，而仅仅需要知道该层间的接口（即界面）所提供的服务。由于每一层只实现一种相对独立的功能，因而可使整个问题的复杂程度下降了灵活性好。当任何一层发生变化时（例如技术的变化），只要层间接口关系保持不变，则该层以上或以下各层均不受影响各层都可以采用最合适的技术来实现易于实现和维护（因为整个的系统已被分解为若干个相对独立的子系统）,1物理层、2数据链路层、3网络层（通信子网）4运输层、5会话层、6表示层、7应用层（资源子网）,OSI参考模型中的数据传输,物理层,物理层提供为建立、维护和拆除物理链路所需要的机械的、电气的、功能的和规程的特性。物理层主要关心的是在连接各种计算机的传输媒体上传输数据的bit流。机械特性指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等等。电气特性指明在接口电缆的各条线上出现的电压的范围。功能特性指明某条线上出现的某一电平的电压表示何种意义。过程特性指明对于不同功能的各种可能事件的出现顺序。,物理层向数据链路层提供服务，主要功能是：物理连接的建立、维护与释放。物理层在设计时涉及的主要问题有：用多大的电压代表“1”或“0”，以及在接收端如何识别出是“1”或“0”确定连接电缆材质、引线的数目及定义、电缆接头的几何尺寸、锁紧装置等指出一个bit占用多长时间？采用什么样的传输方式？初始连接如何建立？当双方结束通信如何拆除连接等,数据链路层,数据链路层传输数据的单位是帧，数据帧的格式中包括的信息有：地址信息、控制信息、数据、校验信息数据链路层的主要作用是通过数据链路层协议（即链路控制规程）在不可靠的物理链路上实现高可靠的数据传输数据链路层把一条有可能出差错的实际链路，转变成为让网络层向下看起来好象是一条不出差错的链路在数据链路层还要控制发送方的发送速率(使接收方来得及接收)，即在数据链路层要解决流量控制的问题网卡是数据链路层的设备,数据链路层的两个子层,为了使数据链路层能更好地适应多种局域网标准，802委员会就将局域网的数据链路层拆成两个子层：逻辑链路控制LLC(LogicalLinkControl)子层媒体接入控制MAC(MediumAccessControl)子层。与接入到传输媒体有关的内容都放在MAC子层，而LLC子层则与传输媒体无关，不管采用何种协议的局域网对LLC子层来说都是透明的,计算机通过适配器和局域网进行通信,硬件地址,至局域网,适配器（网卡）,串行通信,CPU和存储器,生成发送的数据处理收到的数据,把帧发送到局域网从局域网接收帧,计算机,IP地址,并行通信,最初的以太网是将许多计算机都连接到一根总线上。当初认为这样的连接方法既简单又可靠，因为总线上没有有源器件。,载波监听多点接入/碰撞检测CSMA/CD,B向D发送数据,C,D,A,E,匹配电阻（用来吸收总线上传播的信号）,匹配电阻,不接受,不接受,不接受,接受,B,只有D接受B发送的数据,总线上的每一个工作的计算机都能检测到B发送的数据信号。由于只有计算机D的地址与数据帧首部写入的地址一致，因此只有D才接收这个数据帧。其他所有的计算机（A,C和E）都检测到不是发送给它们的数据帧，因此就丢弃这个数据帧而不能够收下来。具有广播特性的总线上实现了一对一的通信。,CSMA/CD表示CarrierSenseMultipleAccesswithCollisionDetection。“多点接入”表示许多计算机以多点接入的方式连接在一根总线上。“载波监听”是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。总线上并没有什么“载波”。因此，“载波监听”就是用电子技术检测总线上有没有其他计算机发送的数据信号。,“碰撞检测”就是计算机边发送数据边检测信道上的信号电压大小。当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。所谓“碰撞”就是发生了冲突。因此“碰撞检测”也称为“冲突检测”。,在发生碰撞时，总线上传输的信号产生了严重的失真，无法从中恢复出有用的信息来。每一个正在发送数据的站，一旦发现总线上出现了碰撞，就要立即停止发送，免得继续浪费网络资源，然后等待一段随机时间后再次发送。当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。A向B发出的信息，要经过一定的时间后才能传送到B。B若在A发送的信息到达B之前发送自己的帧(因为这时B的载波监听检测不到A所发送的信息)，则必然要在某个时间和A发送的帧发生碰撞。碰撞的结果是两个帧都变得无用。,1km,A,B,t,t=B检测到信道空闲发送数据,t=/2发生碰撞,A,B,A,B,t=0A检测到信道空闲发送数据,A,B,t=0,A,B,单程端到端传播时延记为,使用CSMA/CD协议的以太网不能进行全双工通信而只能进行双向交替通信（半双工通信）。每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。最先发送数据帧的站，在发送数据帧后至多经过时间2（两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。以太网的端到端往返时延2称为争用期，或碰撞窗口。经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。,二进制指数类型退避算法(truncatedbinaryexponentialtype),发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。确定基本退避时间，一般是取为争用期2。二进制指数类型退避算法的思路是：发生第1次冲突，等待0-（21-1）个时间片；发生第2次冲突，等待0-（22-1）个时间片；。发生第n次冲突，等待0-（2n-1）个时间片；当重传达16次仍不能成功时即丢弃该帧，并向高层报告。,争用期的长度,以太网取51.2s为争用期的长度。对于10Mb/s以太网，在争用期内可发送512bit，即64字节。以太网在发送数据时，如果发生冲突，就一定是在发送的前64字节之内。若前64字节没有发生冲突，则后续的数据就不会发生冲突。由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于64字节。以太网规定了最短有效帧长为64字节，凡长度小于64字节的帧都是由于冲突而异常中止的无效帧。,当发送数据的站一旦发现发生了碰撞时：立即停止发送数据；再继续发送若干比特的人为干扰信号(jammingsignal)，以便让所有用户都知道现在已经发生了碰撞。,A,B,t,A检测到冲突,信道占用时间,B也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出A发送干扰信号的情况。,数据链路和帧,链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。,IP数据报,10100110,帧,取出,数据链路层,网络层,链路,结点A,结点B,物理层,数据链路层,结点A,结点B,(a),(b),发送,接收,链路,IP数据报,10100110,帧,装入,数据链路层传送的是帧,封装成帧,封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。首部和尾部的一个重要作用就是进行帧定界。,帧结束,帧首部,IP数据报,帧的数据部分,帧尾部,MTU,数据链路层的帧长,开始发送,帧开始,SOH,装在帧中的数据部分,帧,帧开始符,帧结束符,发送在前,EOT,网络层,网络层概述路由算法最优化原则最短路径路由算法洪泛算法基于流量的路由算法距离向量路由算法链路状态路由算法分级路由拥塞控制算法Internet网络层协议,网络层的地位网络层利用数据链路层提供的服务，为传输层提供服务。网络层需要解决的问题是确定分组从源地址到目的地址是如何路由的。在广播网络中，路由选择很简单，所以网络层也很薄，甚至不存在。而在大型网络中，分组不得不跨越若干个网络到达目的地址，这其中的路由问题就需要由网络层来解决。,网络层为了选择路由，需要解决以下问题：屏蔽各种不同类型网络之间的差异需要统一数据格式需要统一网络地址实现全网的数据传输建立跨越网络的虚电路网络之间实现分组的寻址和转发,路由算法,路由算法是网络层软件的一部分子网采用数据报方式，每个分组都要做路由选择。子网采用虚电路方式，只需在建立连接时做一次路由选择。路由算法应具有的特性正确性(correctness)、简单性(simplicity)、健壮性(robustness)、稳定性(stability)、公平性(fairness)、最优性(optimality)路由算法分类非自适应算法(静态路由算法)：按照预先计算好的(off-line)信息进行路由。自适应算法(动态路由算法)：根据网络拓扑结构，通信量等的变化来改变路由。最优化原则(optimalityprinciple)如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由会落在同一路由上。,路径选择技术,分类,分类1,分类2,方式,固定式,对应于接收节点预先（即静态地）规定一条发送路径，算法简单，但不适应网络结构和信息流量的变化。,适应式,在每个节点根据节点和线路的当前状态动态地决定报文分组的传送路径，选择的判定依据通常是使延迟时间最小。这是现在多数报文分组网络采用的方法。每个节点有一路径表，说明从该节点到达其余节点所需传输时间的当前最好估值。下图示意由节点j的延迟时间表Tj（左），生成相应的路径选择表Rj（右），I为收信节点标识，ln为节点J的出口。根据有关网络和信息状态改变路径选择表。,A,I,N,L1L2L3L4,A,I,N,R(I)=minTj(I,ln)ln,各种路径选择算法比较,几种常见的路由算法,静态路由算法最短路径选择(ShortestPathRouting)洪泛算法(FloodingRouting)基于流量的路由算法(Flow-BasedRouting)动态路由算法距离向量路由算法(DistanceVectorRouting)链路状态路由算法(LinkStateRouting)分级路由(HierarchicalRouting),最短路径路由算法,基本思想构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。目的是构建两个路由器间的路由，算法是在子网拓扑图中找出最短路径。得到最短路径，有不同的测量路径长度的方法：计算结点数量计算地理距离计算传输延迟计算距离、信道带宽等参数的加权函数Dijkstra算法是其中的一种计算最短路径的算法。,Dijkstra算法,每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注。开始时，所有结点都为临时性标注，标注为无穷大。源结点标注为0，且为永久性标注，令其为工作结点。检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点。在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点。重复第三、四步，直到目的结点成为工作结点。Dijkstra算法的图例:,Dijkstra算法图例,例：09年全国硕士研究生入学考试计算机统考试题,解,洪泛算法,基本思想:把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。主要问题:洪泛要产生大量重复分组。解决措施每个报头包含站点计数器，每经过一站计数器减1，为0时则丢弃该分组。记录下分组扩展的路径，防止它第二次扩散到已经扩散过的路径中。较实用的方法选择性洪泛算法(selectiveflooding)洪泛法的一种改进：将进来的每个分组仅发送到与正确方向接近的线路上。,应用情况洪泛算法由于过于浪费路由器和线路的资源，在实际应用中很难被直接采用，但还是有一些用处的。在军事领域中，由于需要极好的健壮性，扩散法可以一展身手。在分布式数据库中，有时需要并行地更新所有数据库，这时洪泛算法也是最佳方案。因为洪泛算法总是能够选择最短的路径，可以产生一个最短的延迟。洪泛算法可以作为一种尺度衡量标准来评价其它路由算法。,距离向量路由算法,属于动态路由算法，最初用于ARPANET,DECnet等网络。基本思想：每个路由器维护一张表，表中有每个目的地址的最佳距离和线路，并与邻居结点交换信息来更新表。表(路由表)的构成：包括到达目的结点的最佳输出线路，和到达目的结点所需时间或距离。路由器到邻居结点的“距离”，所用的度量标准可以为站点、估计的时间延迟等。路由器定时向所有邻居结点发送它到每个目的结点的距离表，同时也接收每个邻居结点发来的距离表。根据不同邻居发来的信息，更新本路由器的表。缺陷是存在无穷计算问题,距离向量路由算法图例,路由器J计算到达路由器C的最新路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJKC=6+36=42ms其中JIC是最好的。因此在路由器J的新路由表中填上C的延迟为28ms，经过路由器I。,链路状态路由算法,距离向量路由算法的主要问题由于延迟度量仅仅是队列长度，在选择路由时没有考虑线路带宽。路由收敛速度慢。在1979年前，ARPANET上都采用距离向量路由算法，但是后来为链路状态路由算法所替代。链路状态路由算法的简单步骤发现邻居结点，并获取它们的网络地址。测量到每个邻居结点的延迟或开销。将所有获取的内容封装成一个分组。将这个分组发送给所有其它路由器。计算到每个其它路由器的最短路径。,步骤1：发现邻居结点,发现邻居结点，并学习它们的网络地址。路由器启动后，通过发送HELLO分组，并得到邻居路由器的响应来发现邻居结点。当两个或多个路由器连在一个LAN时，引入人工结点。图例。,步骤2/3：测量线路开销和封装分组,测量到每个邻居结点的延迟或开销，一种直接的方法是：发送一个要对方立即响应的ECHO分组，来回时间除以2即为延迟时间。将所有获取的内容封装成一个分组，即在信息收集完毕后，构造一个包含所有数据的分组。该分组的结构为：发送方的标识符、序号、年龄、邻居结点列表（邻居结点标识符，线路开销值）。创建状态分组的时机:定期创建;发生重大事件后创建。,步骤4：发布链路状态分组,发布算法的基本思想是洪泛链路状态分组。为控制洪泛，每个分组增加一个序号域，每次发送新分组时加1（为了避免序号重复，使用32位的序号）。当一个链路状态分组到达时，若是新的则分发；若是重复的，则丢弃。路由器崩溃后，所有的序号丢失（从0开始记），以后新到分组都可能被当作重复分组而被拒绝。解决序号丢失和出错的方法是增加年龄(age)域，每秒钟年龄减1，至零则丢弃。序号在发送出去后会出现错误，为防止链路出错，所有的链路状态分组都需要应答。,步骤5：计算新路由,在路由器积累了一整套网络的链路状态分组后，就可以通过计算得到整个网络的结构。可以利用Dijkstra算法计算得到每个其它路由器的最短路径。基于链路状态的路由协议OpenShortestPathFirst(OSPF)IntermediateSystem-IntermediateSystem(IS-IS),分级路由,网络规模增长带来的问题路由器中的路由表增大。路由器为选择路由而占用的内存、CPU时间和网络带宽增大。解决办法分级路由对于大型网络分而治之，每个路由器只知道自己所在子网的路由信息，而不去了解其他子网的内部结构。根据需要，可以分成区域(regions)、聚类(clusters)、区(zones)和组(groups)图例。,分级路由图例,小结路由算法,最短路径路由算法在子网拓扑图中找出最短路径。Dijkstra算法洪泛算法把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送基于流量的路由算法根据网络带宽和平均流量，得出平均延迟,距离向量路由算法根据两个结点间的队列长度来完成路由选择，问题是存在无穷计算链路状态路由算法分级路由对于大型网络分而治之，每个路由器只知道自己所在子网的路由信息，而不去了解其他子网的内部结构,拥塞控制,拥塞的基本概念,拥塞(congestion)：网络中存在过多分组的时候，网络性能降低，这种情况被称为拥塞。报文装配死锁：收信机的缓冲器被占满，任何报文都装配不起来，形成既无法交付报文，后续分组也进不来的情况,存储转发死锁：中继缓冲区装满后，造成“输不进，出不去”的局面,造成拥塞的原因多个输入对应一个输出慢速处理器低带宽线路拥塞控制(congestioncontrol)与流量控制(flowcontrol)拥塞控制需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素。流量控制与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，一般都是基于反馈进行控制的。,拥塞控制的分类,根据控制论，拥塞控制可分为两类。开环控制(防患于未然)通过良好的设计解决问题，以避免拥塞发生。进行开环控制需要决定何时接收新的分组、何时丢弃分组、丢弃哪些分组。利用开环进行拥塞控制时，所有这些操作都不会考虑网络的当前状态。闭环控制(因地制宜)基于反馈机制。其工作过程为：监控系统，发现何时何地发生拥塞。把发生拥塞的消息传给能采取动作的站点。调整系统操作，解决拥塞问题。,开环控制通信量整形,通信量整形(TrafficShaping)的基本思想网络上，突发的通信量是造成拥塞的主要原因。强迫分组以某种可以预见的速率传送，减少拥塞，这种方法被称为通信量整形。漏桶算法和令牌桶算法都可以实现通信量整形。漏桶算法(TheLeakyBucketAlgorithm)基本原理：图例。在计算机中的使用漏桶有限内部队列；水通信量，需要发送的分组。分组到达队列时，队列满，分组被丢弃；队列空，分组放置在队尾。效果将用户发出的不平滑的分组流转变成网络中平滑的分组流。漏桶算法既可以用于分组长度固定的协议（如ATM使用分组计数），也可用于可变长分组的协议（如IP使用字节计数）。,无论水流进桶的速度为多少，只要桶中有水，水从桶中外漏的速度是恒定的。桶空了，速度为零。桶满了，水外泄。,漏桶算法,令牌桶算法,由于漏桶算法不够灵活，因此加入令牌机制。令牌桶算法基本思想：漏桶存放令牌，每T秒产生一个令牌，分组发送之前必须获得一个令牌，传输之后删除该令牌。,漏桶和令牌桶算法的比较,通信量整形策略不同漏桶算法不允许空闲主机积累发送权。令牌桶算法允许空闲主机积累发送权，以便以后发送大的突发数据，最大为桶的大小。桶中存放的内容不同漏桶中存放的是数据，桶满了丢弃数据。令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据。,闭环控制,闭环控制需要完成：何为拥塞、如何反馈和如何解决。何为拥塞衡量网络拥塞的参数缺乏缓冲区造成的丢包率平均队列长度超时重传的分组数目平均分组延迟分组延迟变化(Jitter)如何反馈反馈方法向负载发生源发送一个报警分组，这同时加强了拥塞。在分组结构中保留一个位或域来表示发生拥塞，一旦发生拥塞，路由器将所有输出分组的拥塞位填充，报警。主机或路由器主动地、周期性地发送探报(probe)，查询是否发生拥塞。如何解决利用拥塞控制算法,闭环控制虚电路子网中的拥塞控制,方法一:许可控制(admissioncontrol),一旦发生拥塞，就不允许再建立新的虚电路，直到拥塞解除为止。方法二:在发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区。方法三:资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。,闭环控制抑制分组,抑制分组(ChokePackets)路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态。每个新分组到来，检查它的输出线路是否处于警戒状态。若是，向源主机发送抑制分组，分组中指出发生拥塞的目的地址。同时将源分组打上标记(为了以后不再产生抑制分组)后，正常转发。源主机收到抑制分组后，按一定比例减少发向特定目的地的通信量，并在固定时间间隔内忽略指示同一目的地的抑制分组。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制分组；若在监听周期内没有收到抑制分组，则增加通信量。通常采用的通信量增减策略是：减少时按一定比例减少，保证快速解除拥塞。增加时以常量增加，防止很快导致拥塞。,由于采用抑制分组时，源端的抑制行为是自