计算机通信网网络层课件.ppt
计算机通信网,网络层2,作者：段景山 杨宁 毛玉明,2,网络层,网络层的背景与功能实现路由功能的要素路由表与RoutedRouting 路由算法拥塞控制互联及网络互联,3,5.4 Routing路由算法,基本方法事先计算所有最优路由，形成路由表(转发表）各节点根据路由表进行PDU的转发,2,1,3,4,5,6,4,Routing 路由算法,静态路由算法动态路由算法矢量距离算法链路状态算法分级路由机制特殊问题的路由方法广播数据的路由多点播送移动主机,重,5,路由算法,5.4.1静态路由,不测量也不利用网络信息，而是采用固定规则选择,静态路由在网络发生变化时，往往由人工修改路由,路由表内容保持不变,节点间不交换路由信息,简单，灵活性差,适用于小型、简单、拓扑不发生重大改变的网络情况,6,静态路由,路由算法,工作方式：某个接口进的PDU，转发到其余所有接口；目的节点会收到多个重复报文。特点：不需要网络拓扑信息-网络结构无关性总能够送到目的地-高度稳健性所有节点都能收到-可用于广播防止无休止地转发PDU-PDU生命期(Time To Live, TTL)网络上PDU几何级数膨胀-网络负担重，小网适用适合树形，星形网络,泛射方法洪泛flooding,不测量也不利用网络信息,7,泛射方法,减轻泛射冗余量的方法不向来路转发延迟发送比较接收报文以确定重复报文生存时限减少在环路上的浪费报文序号通过序号判断重复的报文,2,1,3,4,5,6,关,8,静态路由,固定路由方法,路由算法,1）事先计算所有节点间的最优路径，形成中心路由选择表,6,5,4,3,2,1,6,5,4,3,2,1,源节点,目的节点,下一个节点,不测量也不利用网络信息,9,静态路由,2)每个节点形成路由转发表,不测量也不利用网络信息,路由算法,10,3)路由表可由人工配置，除非必要时由人工修改可设置几个备用路由,静态路由,2,1,3,4,5,6,不测量也不利用网络信息,路由算法,11,静态路由,随机路由,不测量也不利用网络信息,工作方式： 从多个（能到达目的地的）出口中随机选中一个来转发PDU。 随机概率 - 根据信道负载、不需要网络拓扑信息-网络结构无关性每次路径是随机变化的适合树形，星形网络一般不单独使用，配合其他协议，可以达到负载均衡的效果,路由算法,12,5.4.2动态路由算法,网络的变化较频繁网络的规模较大网络的拓扑复杂根据网络运行的情况，动态更新路由表,路由算法,13,动态路由,独立路由选择最短等待法反向学习法中心路由分布式路由矢量距离法线路状态法,路由算法,重,14,动态路由,独立路由选择不交换路由信息，可动态（非人工）改变路由适应变化最短等待法根据端口的当前状态选择路由通断、队列长度、权值反向学习法根据源地址学习到源的路径,路由算法,15,反向学习法,C,A,收到从A送来的报文,路由表中记录下从该接口可以到达A,在PDU中增加距离记录，每经过一个节点，距离加1，供反向学习选择最佳路由。特点：自适应路由算法，能逐渐形成最佳路由动态适应新节点的加入对节点、链路故障反应迟钝对拓扑稳定、小型网络适用,A,左,dn,路由算法,16,动态路由,中心路由（集中路由）,2,1,3,4,5,6,中心路由计算机,工作方式： 各个节点定期把自己的信道、相邻节点情况报告中心路由计算机，由计算机计算出各节点到其余节点的最佳路由，然后把路由表分发到各个节点上。特点：最佳路由-理想路由信息上报、更新同步困难（特别是大网）,路由算法,17,动态路由,分布式路由基本原理主动与其他节点交换路由信息路由协议节点独立计算最优路由分布式放弃全局最优、寻求局部最优化交换的信息越详细、交换的频率越快，路由优化越好，对网络带来的额外开销也越大。寻求在额外开销和反应速度间的平衡,*可行性：分布计算能否统一？ 最佳路由法则：（利用相同的信息，相同的算法） 若A认为到D的最佳路由要经过B，则B有相同的看法。,重,18,分布式路由,分布式路由分析分布式路由的不利之处：利用部分路由信息，无法得到全局最优路由可能出现相互矛盾的路由反应快会造成路由震荡，反应慢则好处不大有利方面：局部范围，网络额外开销少可在局部获得最佳路由较准确，不需人工干预自动化,重,19,分布式路由,分布式路由算法要点,交换路由信息,分布式计算：最优路由计算方法,哪些信息？,交换方式,边交换信息边计算,可达、距离、费用、负载、延时,关,20,分布式路由,常见的分布式路由：基于网络距离的分布式路由算法-矢量距离法基于信道状态的分布式路由算法-线路状态法,重,21,5.4.3 距离矢量算法,以中继节点个数为度量,2,1,3,4,5,6,1,1,1,1,1,1,1,1,交换路由信息,1,3,工作方式：每个节点自动找出相邻节点，形成初始路由表，距离为1每个节点定期和相邻节点交换路由信息路由及距离根据收到的路由信息，更新到其他节点的路径（最短距离）通过不断扩散，逐渐形成到所有节点的路由,22,距离矢量算法,初始化，各节点形成各自的本地信息即邻接路由器扩散，各节点向邻居节点扩散已知的路由信息计算，各节点根据邻居节点扩散来的信息计算新的路由距离更新=到邻居节点的距离+邻居节点到目的节点的距离不断扩散，各节点定期不断向邻居扩散自己已知的路由信息,对比,23,距离矢量算法,节点1路由表更新,初始值,收到节点3路由信息,更新后,收到节点2路由信息,距离更新=到邻居节点的距离+邻居节点到目的节点的距离,更新后,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,4,2,2,5,3,2,关,24,距离矢量算法,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,关,25,距离矢量算法,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1路由表更新,距离更新=到邻居节点的距离+邻居节点到目的节点的距离,收到节点2路由信息,更新后,6,2,4,更新后,6,2,4,3,3,关,26,距离矢量算法,交换信息节点所知的全网可达信息交换路由表（路由转发表）路由信息：目的距离（节点个数）即通过“我”能到达哪些节点，有多远交换方式仅与相邻节点交换，定期交换与相邻路由器交换全网路由信息最佳路由计算方式每个节点告诉“我”的，都是他们的最佳路由。根据当前已知的，对比新知道的，算出最好的当前知道：到D经过C，总距离为5新了解到：B告诉“我”，经过他到D距离为2“我”到B的距离为2， 所以“我”到D的路由更新为：经过B到D，路由距离为4,重,27,距离矢量算法,几个相关问题如何交换路由信息何时？定期邻居失效 / 发现新邻居时和谁？邻居节点水平分割节点没有必要将从某节点收到的信息再传回给该节点无穷计数距离矢量算法会出现路由环路设计最大路径长度，以减轻环路出现时带来的损害用毒性反转方法，破坏路由环路,28,水平分割,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,节点没有必要将从某节点收到的信息再传回给该节点,29,无穷计数,在某种情况下，距离矢量算法可能出现路由环路，其现象是路由表项随路由信息更新，不断增加。,A,C,B,D,正常情况：,A认为到D经过B,C认为到D经过B,B认为到D经过D,路由环路：,A认为到D经过B,C认为到D经过A,B认为到D经过C,30,A,C,B,D,平时：A收到C告知：D有两跳A收到B告知：D有一跳,选B,C收到A告知：D有两跳,C收到B告知：D有一跳,选B,当B到D的链路断掉后，一种可能的情形：,B告诉A、C：D不可达,A重新选路，正好收到C告知D有两跳（C还没收到B的更新信息）,A选择到D经过C，距离为三跳,A告知B：D有三跳,B选择到D经过A，距离为四跳,C收到B先前的D不可达更新，重新选路,B告知C：D有四跳,C选择到D经过B，距离为五跳,出现路由环路，并计数到无穷大,难,31,毒性反转解决路由环路,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,节点1当前的路由表,节点1向节点2发布的路由信息,节点1向节点3发布的路由信息,节点将从某节点收到的信息再传回给该节点时，告诉对方不能从我这里过,无穷大,无穷大,无穷大,扩,32,距离矢量算法,特点：只与邻节点交换路由信息各节点独立计算最优路径能适应网络拓扑的变化稳定后，形成最短路径算法简单缺点：网络变化扩散到全网速度慢扩散时间：所有节点都发现变化的速度路由收敛慢收敛时间：大家分别计算，结果达到统一的速度存在路由环在网络变化未扩散完全时。,小网,对比,重,33,5.4.4链路状态算法,以线路的延时作为链路度量延时比节点数更能反映网络和信道的实际状况从发出PDU到收到应答来测量延时及变化线路的速率、当前负载节点处理能力-会影响延时能较好地防止网络拥塞现象、均匀分布网络流量工作方式： 从每个节点探询相邻节点，得到延时(链路状态)初始值 每个节点定期和所有节点交换路由信息探询的相邻节点链路质量 根据收集到的路由信息，计算到其他节点的路径（最小延时）,重,34,链路状态算法,2,1,3,4,5,6,4,3,5,6,1,1,4,2,10,22,交换链路质量与全网的所有节点交换,充实路由信息库“绘出”网络拓扑,计算路由表,来自1: A、B信息,A,B,来自2: A、C、D信息,来自3: B、C、E、F信息,来自4: D、E、G、I信息,来自5: F、G、I、J信息,自己测得的 I、J,I,J,C,D,E,F,G,测量链路质量,对比,35,链路状态算法,2,1,3,4,5,6,4,3,5,6,1,1,4,2,10,22,关,36,链路状态算法,交换的信息与相邻路由器之间的链路质量（延时）交换方式与全网路由器之间交换有控制的泛射向全网路由器宣告相邻路由信息最佳路由的计算方法收集信息形成路由信息库利用最短路径算法计算路由以本节点为源当发现链路质量变化时，更新信息库看改变的路由对当前的各条最优路由是否造成影响，并更新,重,37,链路状态算法,几个相关问题如何测量线路开销如何发布链路状态分组如何计算最佳路由,38,链路状态算法,如何测量线路开销利用echo分组的延时来评估是否计入载荷从开始排队算起？从开始发送算起？,A,B,T,39,链路状态算法,如何发布链路状态分组何时？定期链路状态发生改变时和谁？全网节点怎样才能和全网节点交换？洪泛，但是在相当的控制之下每条信息有序号，节点收到相同序号的信息就丢弃每条信息有发布时间，节点同时收到多条信息时，只处理时间较近的一条,2,1,3,4,5,6,重,40,链路状态算法,如何计算最佳路由最短路径算法Dijstra算法,A1,A2,A4,A3,A5,2,6,5,1,2,1,5,1）初始化时，设A1到其它不直连顶点距离为,寻找A1到所有节点的最短路径,A2,A3,A4,A5,顶点,距离,路径,2）选择距离最短的路径,3）观察通过新选择的路径是否能更短到达其它顶点,4）选择出的最短路径将不参加下一轮比较,5）反复2 - 4步，直到不剩有顶点,2,6,5,A2,A3,A4,A1 A2 A33,更新,A1 A2 A3,3,A1 A2 A4 ,A1 A2 A5 4,A1 A2 A3 A44,更新,A1 A2 A3 A4,4,A1 A2 A3 A58,A1 A2 A5,4,A1 A2 A3 A4 A5,更新,难,41,链路状态算法,最短路径算法的计算思想每一步都取出当前最短的路径，计算该路径对其它路径的改变从最近开始逐步计算到最远,2,1,3,4,5,6,关,42,链路状态算法,特点与全网节点交换路由信息路由信息的扩散各节点独立计算最优路径一致性、准确性有较好的保证不是建立在别人的计算结果上（如距离矢量算法）能适应网络拓扑的变化，稳定后能形成最短路径收敛速度快可在大网中使用不是计算之后再扩散算法复杂，存储空间需求大需要记录全网所有的链路状态,对比,重,43,5.4.5分级路由体系,网络规模大巨型网络,建设结构、管理机构等众多,网络结构复杂,各自进行各自的路由,网间设定网间的路由方式,分级路由体系,屏蔽网内路由细节,考虑网间路由的一些管理性特点,网间路由,44,5.4.6 一些特殊的路由问题,广播数据的路由多点播送数据的路由移动主机的路由策略无线多跳网的路由技术,45,广播数据的路由,广播数据需要发送给所有目的地的分组实现方法类型向每个目的发送一份拷贝洪泛多目的分组路由广播分组带有所有希望的目的路由器选择适当线路生成树按树的路径转发分组没有回路,46,多点播送路由选择,多点播送小组,生成树,小组1的多点播送树,小组2的多点播送树,47,多点播送路由选择,播送树有源树组播组里，每个发送源都形成一颗组播树有源树组播路由器在转发数据时，根据分组源地址和相应的树表，决定转发的路径共享树核心基本树在组播组里，大家遵循同一颗组播树共享树组播源站先想办法将数据发送到共享树的根节点，由根节点再延着树转发数据减少树表所占空间组播树的形成协议,1,1,1,1,1,源,源,1,1,1,1,根,1,扩,48,反向路径转发工作方式路由器收到组播分组时，在树表中查本机到达源地址所用的接口若收到分组的接口与查到的接口是一致的，则转发组播分组到树的其它接口，否则丢弃目标减少组播分组的转发个数基本思想：若源节点在树上，基本上可以放心转发，即不是环路上传过来的,多点播送路由选择,1,1,1,1,1,扩,49,组播标准,组播地址IP组播地址：224.0.0.0239.255.255.255（D类）MAC组播地址：0 x0100.5Exx.xxxx映射：IP地址的后28位MAC地址的后23位（25:1）组播路由协议密集模式（Push，SPT）：DVMRP、PIM-DM稀疏模式（Pull，RPT）：PIM-SM、CBT链路状态协议（SPT）：MOSPF组播组管理协议IGMP：v1、v2、v3,50,移动主机的路由策略,寻径与移动的矛盾节点的网络地址一般具有定位性当节点移动后，无法通过节点的地址对节点定位，也就无法将数据路由到节点。本地代理、外地代理,本地代理,A,B,外地代理x,注册,通知A在我这里,A在x处,51,无线多跳网络的路由技术,无线多跳网络Ad Hoc网络特点拓扑复杂，多变，变化速度快路由技术先应式：表驱动式，先建立路由表反应式：按需路由，只有当需要时才去发现路由,扩,52,其它路由算法,负载分担路由协议边界路由协议,昂贵的长途干线可节省,53,5.4.7路由算法的应用,网间路由（大型网络）链路状态算法网络拓扑结构复杂,网间路由,54,路由算法的应用,网间路由（中小型网络园区网）距离矢量算法简单,Router,Router,Router,55,路由算法的应用,以太网桥中的路由： 洪泛路由+自学习路由,56,5.5 拥塞控制,网络拥塞当节点阻塞时，将蔓延到全网，使网络吞吐能力下降,网络流量过于集中，超过信道传输能力,流量,吞吐量,理想,网络流量过于集中，超过节点处理能力,57,拥塞,一个点的拥塞会向全网蔓延,关,58,5.5.1拥塞控制与流量控制,拥塞控制不同于流量控制控制对象不同流控：局部于两点之间拥控：全局控制，拥塞点附近节点全网范围控制结果不同流控：两点之间发送方降速拥控：拥塞点得到缓解控制方法不同流控：降低发送速度拥控：预分配资源，更改路径，丢弃分组等,重,59,拥塞控制与流量控制,拥塞控制与流量控制之间有联系，易混淆网络拥塞后，吞吐量下降，节点响应慢，感觉象对方收不下来，从而误判为需要流量控制流量控制的不好是造成拥塞的原因之一在拥塞控制机制中，可能用到流量控制手段但拥塞控制事关全局，仅在个别节点的个别链路上进行流量控制，并不能有效解决网络拥塞问题,重,60,5.5.2拥塞控制的基本方法,预防和避免开环不使拥塞出现的方法缓冲区预分配分组丢弃网络分组定额控制检测和解除闭环如何检测拥塞的出现检测丢失、延时、队列长度等出现拥塞后的解决方法拥塞后不许可，如不给拨号音另选路径抑制分组载荷脱落,重,注意：影响拥塞控制的策略,61,5.5.3 影响拥塞控制的策略,相关方面很多,重,62,5.5.4虚电路子网的拥塞控制,准入控制拥塞时不再建立新的链路拥塞时选择绕道建立虚电路,扩,63,5.5.5数据报子网的拥塞控制,基本思想当线路利用率超过阈值，路由器通知源站减速线路利用率计算：u新 a u旧（1a）f相关技术警告位源通过收到带警告确认的个数调整发送速率抑制分组拥塞路由器通过抑制分组直接通知源站降速逐跳抑制源太远时，通过从拥塞点向外逐跳抑制,扩,64,5.5.6 负载丢弃,基本思想拥塞路由器根据一定策略丢弃分组相关策略葡萄酒策略：老酒更醇，即丢弃新分组文件传输牛奶策略：新鲜更重要，丢弃老分组流媒体其它“智能”策略,扩,65,5.5.7通信量整形,基本思想强迫分组以某种可预见的速率传送调整用户数据为可控的匀速速率方法流说明：用户与网络之间协商控制参数允许传输速率、突发特性、丢失允许情况漏桶算法：以匀速间隔向网络送入数据，可以任意速率接收用户数据,时快时慢,时多时少,匀速,66,5.5.8多点播送的拥塞控制,RSVPResource reSerVation Protocol适合电视会议，视频点播的多点播送拥塞控制多源对多组接收接收者可自由切换“频道”基本思想：尽量减少源发出的数据避免造成拥塞基于多点播送生成树由接收者向源及路径上的路由器申请带宽同源接收者可利用同一路径及带宽,67,RSVP多点播送树,68,RSVP资源保留,主机5在申请到主机1的播送带宽时,可以部分利用主机3已申请的带宽从主机1到路由器H,69,5.5.9QOS保证,综合服务区分服务MPLS。,扩,70,作业,如果我们把交通路口看作是网络中的节点，道路看作是网络中的链路，拥塞问题和城市交通堵塞问题非常类似，请你从日常生活中常见的交通堵塞中例举出一些造成堵塞的原因。思考这些因素是否也会出现在网络中。,
