《计算机通信网 》第5章 网络层2

3.4分级路由体系(简单了解)大型网络可能成百上千(或更多)的路由节点不适宜只实施一种路由协议分级：分而治之分级：Domain、Area、…分级路由域内路由：通常情况域间路由每个域规定一个“指派路由器”参与域间路由信息交互域间拓扑结构每个域看做一个“节点”为指派路由器规定“邻居”关系域间路由协议在指派路由器间运行路由协议Domain-1Area-0Area-1Area-2Area-3Domain-2指派路由器13.5一些特殊的路由移动主机的路由策略广播数据的路由多点播送数据的路由无线多跳网的路由技术2主机从一个位置移动到另一个位置下的通信网络中路由选择结果，分组只能送到主机原来位置不可能因主机移动，让网络所有路由器修改FIT移动主机路由(简单了解)主机主机移动主机分组传输失败3移动主机路由移动路由解决方案设置“家乡代理”和“外地代理”家乡代理登记主机外出情况和外出位置外地代理接受主机移动进入，并向它的家乡报告家乡代理截获到移动主机的分组，转交到外地代理不能直接转交分组只能把分组作为“数据”封装到另一个分组上传(隧道技术)外地代理把分组递交到移动主机移动主机发出的分组按常规路由主机主机移动主机家乡代理外地代理家乡代理外地代理移动主机代理通告移入请求移动登记确认移入许可固定主机分组分组(隧道)分组分组4移动主机路由事例本地代理AB外地代理x注册通知A在我这里A在x处5广播路由广播：分组送达网络所有节点实现方法独立向各个节点发送一份拷贝(十分低效)多目标分组广播分组格式有多个目的地址项路由器按地址项分别选择路径洪泛(已讲述，效率较低)生成树链路设置成是否允许转发广播分组允许转发的链路构成网络的一颗树广播按树转发(高效)逆向路径转发6多播路由选择多播组的含义一组节点(既不是所有节点，也不是单个节点)组的划分不固定，可动态形成节点可自由加入一个或多个组多播路由(要求路由器具备多播功能)将分组路由到指定组的所有成员路由算法：多播树应用示例DV路由组(用多播与邻居交换信息)SPF路由组(可用多播路由取代扩散算法)其它应用(见书中内容)多播组1多播组2多播组3多播组47多播路由选择多播组组成员不固定，节点可自由加入一个或多个组多播数据—向一个组发送的数据多播路由：向一个组发送的路由算法称多播路由多播路由的实现：播送树（多播树）信源树路由算法核心树路由算法（共享树）生成树小组1的多点播送树小组2的多点播送树8多点播送路由选择信源树组播组里，每个发送源都形成一棵组播树－－有源树组播节点在转发数据时，根据分组源地址和相应的树表，决定转发的路径共享树－－核心基本树在组播组里，大家遵循同一颗组播树－－共享树组播源站先想办法将数据发送到共享树的根节点，由根节点再延着树转发数据减少树表所占空间组播树的形成－－协议11111源源1111根19组播标准组播地址IP组播地址：224.0.0.0~239.255.255.255（D类）（11100000）（11101111）MAC组播地址：0x0100.5Exx.xxxx0100.5E00.0000----0100.5E07.FFFF映射：IP地址的后28位MAC地址的后23位（25:1）组播路由协议密集模式（SPT-有源树）：DVMRP、PIM-DM稀疏模式（RPT-共享树）：PIM-SM、CBT链路状态协议（SPT）：MOSPF组播组管理协议IGMP：v1、v2、v310无线多跳网络－AdHoc网络站点可以自由移动无线信号传播范围有限动态变化的拓扑结构路由技术如果站点移动速度缓慢—拓扑缓慢变化改进的DV路由算法—DSDV、OLSR如果站点移动速度较快—拓扑变换较快DV路由算法不可用SPF算法不可用确定临时路由的路由算法(按需路由、反应式路由)AODV：用扩散法寻找目的节点，利用返回的应答建立路由无线多跳网络的路由技术扩11作业11、简述在距离矢量算法（D-V）和链路状态算法（L-S）中，各节点计算路由转发表时，各以什么为依据？并以此分别说明采用D-V和L-S算法的节点对网络拓扑的了解情况。2、下图中以延迟为代价，请用D-V算法和L-S算法分别计算C点的路由转发表（要求答题步骤：初始表，收到中间信息后，路由的变化过程，以及稳定后C点的路由表）ABEDC5311221124拥塞控制拥塞问题拥塞控制策略拥塞控制方法开环控制闭环控制服务质量（QoS）保障技术服务模型13144.1拥塞问题拥塞现象一种常见的主机接入结构如图各站点都用100Mbps信道连接网络设备网络设备只有一条100Mbps信道连接到网络其它部分平均来看，每台主机仅有25Mbps的通信容量若某个时间段T内，各主机传输的数据速率总和超过100Mbps，那么，网络设备上将出现数据的堆积r1r2r3r4100Mbps网络∑ri≥100Mbps100Mbps100Mbps100Mbps100Mbps假速率144.1拥塞问题拥塞现象网络流量过于集中到某些节点和链路链路：分组太多，超过我的能力了！节点：分组太多，受不了了！154.1拥塞问题拥塞原因问题1：信道过载问题问题2：节点过载问题B当多条路由经过同一个节点，传输的数据总量超过该节点的分组处理能力，分组将在节点B处堆积。结果同上Br1rnRT∑ri≥RT路由当多条路由经过同一条链路，传输的数据量超过该链路的总容量时，分组将在节点B处堆积。结果1：分组堆积量超过节点A存储能力结果2：各条路由的实际传输能力下降RPrjrirk节点B的分组处理能力为RP(分组/秒)链路的传输容量为RT(分组/秒)输入分组速率ri(分组/秒)问题1和问题2是两个本质不同的独立问题问题1需要用路由算法解决(或链路扩容)问题2需要升级节点处理能力∑ri≥RP16★4.1拥塞问题分组堆积假设链路都是100Mbps，每个站点发送的速率都是25Mbps，在网络设备上是否会出现分组堆积？25Mbps100Mbps25Mbps25Mbps25MbpsT1T,说明路由器中出现了短暂的堆积现象由于传输空缺现象，路由器实际传输速率100Mbps,随着空缺的继续出现，路由器中的分组堆积愈加严重(输入端保持100Mbps)T站点1站点2站点3站点4站点发送情况T1路由器发送情况非均匀的突发流量17分组堆积：排队论模型分组到达服从均值为λ的泊松分布pn(τ)：在时间间隔τ内有n个分组达到的概率分组队列到达分组按顺序排队，依次接受服务服务一次服务一个分组，单位时间内可服务R个分组18客户队列服务生分组到达!)()(nepnn18分组堆积-排队论模型分组平均排队长度分组平均等待时间分析理解λ/R表示：分组平均到达数与服务能力的比值(负载率)当r接近R时，排队延时急剧上升当平均通信量达70%时，该考虑信道容量升级了！否则，排队现象将降低网络服务质量19)(,1RRNRRNRT11194.1拥塞问题-小结拥塞原因分组在设备上堆积、丢弃导致源节点超时重传信道有效速率降低拥塞后果超过临界点，有效吞吐率降低入网流量进一步加剧拥塞最终导致网络瘫痪完美情况网络流量小于网络最大负荷时，所有通信量能全部通过网络流量超过网络最大负荷时，网络能以最大负荷工作期望情况网络对流量的承载能力接近完美曲线流量吞吐量理想100%100%拥塞拥塞控制期望效果204.2拥塞控制策略涉及四个方面上层(网络层之上)控制：适当降低通信量（后一章内容）路由协议控制：最佳路由策略(应尽可能分散路径)如LS协议：尽可能选择不同“等距路径”网络层控制：预防或处理分组堆积预防分组堆积、堆积后处理流量处理：流量整形突发流量更易产生拥塞降低通信量路由：将路径分散拥塞：分组堆积214.2拥塞控制策略影响拥塞控制的策略层策略集传送层重传策略乱序缓存策略确认（应答）策略流控制策略确定超时的方法网络层虚电路子网vs数据报子网分组排队和服务策略分组丢弃策略路由选择算法分组生存期管理数据链路层重传策略乱序缓存策略确认（应答）策略流控制策略224.2拥塞控制策略拥塞控制与流量控制相互影响流量控制的不好是造成拥塞的原因之一网络拥塞导致目的节点响应慢，误判为需流量控制拥塞控制与流量控制的差异控制对象不同流控：局部于两点之间拥控：全局控制，拥塞点－附近节点－全网范围控制结果不同流控：两点之间发送方降速拥控：拥塞点得到缓解控制方法不同流控：降低发送速度拥控：预分配资源，更改路径，丢弃分组等★234.3拥塞控制方法★开环控制模型：预防和避免节点资源调度流量整形分组丢弃…闭环控制模型：检测和解除(检测到(将)拥塞时采取措施)检测丢弃、延时、队列长度等准入控制、另选路径拥塞通知、分组抑制负载(分组)丢弃…拥塞控制节点拥塞控制节点拥塞检测24开环控制通信量整形（Shaping）对突发通信量进行平滑(削峰填谷)，增加预见性，有利于减少拥塞通信量整形技术漏桶算法间隔T发送一个单位信息桶满时溢出(丢弃)桶空时无流量实际通信量平滑通信量输入速率(随机变化)分组漏桶：恒定分组速率字节漏桶：恒定字节速率桶空T输出速率证明：当输入速率的均值等于输出速率(1/T)时，桶中将始终有数据在排队25开环控制—通信量整形令牌桶算法—漏桶改进算法每T秒产生一个令牌，存放在漏桶中，令牌累积到漏桶上界时就不再增加（令牌桶容量）每发送一个信息（字节或分组）消耗一个令牌没有流量时，保留令牌以等待流量出现有流量没有令牌时，等待令牌产生允许突发流量恒定速率产生令牌连续流出积累令牌信息队列连续发送的信息（分组）数=f(令牌速率，桶容量，输出速率）T令牌桶26开环控制—通信量整形令牌桶允许的突发流量长度计算设：漏桶的容量为C、最大漏出速率为M、令牌的输出速率为p，突发时间长度为S？漏出的最大数据量=漏完满桶+新增的量=C+pSS时间内以最大漏出速率漏出的量=MS故有C+pS=MS由此求得：S=C/(M-p)2Mbps250kb25Mbps最大突发长度(25M速率)=11ms当令牌产生的速率p接近最大漏出速率M时，最大突发长度将急剧增长2728开环控制—通信量整形漏桶算法与令牌桶算法的区别流量整形策略不同漏桶算法不允许积累发送权，以便发送大的突发数据令牌桶算法允许，最大长度与桶的大小和令牌产生速率有关桶的作用不同漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。29开环控制—随机早期丢弃(RandomEarlyDetection)控制排队长度的技术当排队长度小于L1时，到达的分组进入排队当排队长度大于L1、小于L2时，随机丢弃进入的分组当排队长度大于L2时，丢弃所有进入排队的分组分组丢弃概率p，随队列长度增加，丢弃概率相应增加L1L2L1L1L2L1L2p01分组丢弃算法到达分组x=uniform[0,1]排队，当xp丢弃，当x≤p30闭环控制—源抑制基本思想路由器监控输出线路及其它资源的利用情况（拥塞检测），当利用率超过某个阈值时，路由器通知源站减速控制源头，降低入网的分组量速率控制方式（AIMD）按一定比例a降速，保证快速解除拥塞；以常量m增加，防止很快导致拥塞。当收到拥塞通告时：f新=a·f旧，0a1(快速降低)当不再收到拥塞通告时：f新=f旧+m(缓慢增加)源节点拥塞检测中间节点拥塞控制拥塞通告分组流量31闭环控制—源抑制如何通知源节点设置警告位（隐性通告）分组中包含拥塞警告位，拥塞节点将其置位，目的节点将该信息回传给源节点（在确认分组头部设置警告位）有意见认为这样反馈太迟钝了抑制分组（显性通告）向源发送抑制分组，指出发生拥塞的目的地址，同时将原分组打上标记（后续节点不再产生抑制包），正常转发有意见认为由于存在多个源，这会使网络负担增加源节点拥塞检测中间节点拥塞控制抑制分组警告位通知源节点目的节点警告位警告位32闭环控制—逐跳抑制基本思想抑制分组对它经过的每个路由器都起作用；能够迅速缓解发生拥塞处的拥塞；上游路由器要求有更多的缓冲区；在高