计算机通信网-网络层-part2

计算机通信网网络层2作者:段景山

杨宁

毛玉明2

网络层网络层的背景与功能实现路由功能的要素路由表与RoutedRouting路由算法拥塞控制互联及网络互联35.4Routing路由算法基本方法事先计算所有最优路由，形成路由表(转发表)各节点根据路由表进行PDU的转发213456目的节点出口下一节点4Routing路由算法静态路由算法动态路由算法矢量距离算法链路状态算法分级路由机制特殊问题的路由方法广播数据的路由多点播送移动主机重5路由算法5.4.1静态路由不测量也不利用网络信息,而是采用固定规则选择静态路由在网络发生变化时,往往由人工修改路由路由表内容保持不变节点间不交换路由信息简单,灵活性差适用于小型、简单、拓扑不发生重大改变的网络情况6静态路由路由算法工作方式：某个接口进的PDU，转发到其余所有接口;目的节点会收到多个重复报文。特点：不需要网络拓扑信息---网络结构无关性总能够送到目的地---高度稳健性所有节点都能收到---可用于广播防止无休止地转发PDU---PDU生命期(TimeToLive,TTL)网络上PDU几何级数膨胀---网络负担重，小网适用适合树形，星形网络泛射方法 洪泛

flooding不测量也不利用网络信息7泛射方法减轻泛射冗余量的方法不向来路转发延迟发送－－比较接收报文以确定重复报文生存时限－－减少在环路上的浪费报文序号－－通过序号判断重复的报文213456关8-12-23242424静态路由固定路由方法路由算法1)事先计算所有节点间的最优路径，形成中心路由选择表12453617232211331142856385654321654321-655425-554254-542535-325424-254151-源节点目的节点下一个节点不测量也不利用网络信息9静态路由2)每个节点形成路由转发表节点1目的节点下一节点2232425262节点2目的节点下一节点1133445464节点3目的节点下一节点1524455566节点4目的节点下一节点1122355565节点5目的节点下一节点1424334466节点6目的节点下一节点1525354555不测量也不利用网络信息路由算法103)路由表可由人工配置,除非必要时由人工修改可设置几个备用路由静态路由213456不测量也不利用网络信息路由算法11静态路由随机路由不测量也不利用网络信息工作方式：

从多个（能到达目的地的)出口中随机选中一个来转发PDU。

随机概率---根据信道负载、…不需要网络拓扑信息---网络结构无关性每次路径是随机变化的适合树形，星形网络一般不单独使用，配合其他协议，可以达到负载均衡的效果路由算法125.4.2动态路由算法网络的变化较频繁网络的规模较大网络的拓扑复杂根据网络运行的情况,动态更新路由表路由算法13动态路由独立路由选择最短等待法反向学习法中心路由分布式路由矢量距离法线路状态法路由算法重14动态路由独立路由选择不交换路由信息，可动态（非人工)改变路由适应变化最短等待法根据端口的当前状态选择路由通断、队列长度、权值……反向学习法根据源地址学习到源的路径路由算法15反向学习法CA收到从A送来的报文路由表中记录下从该接口可以到达A

在PDU中增加距离记录，每经过一个节点，距离加1，供反向学习选择最佳路由。特点:自适应路由算法，能逐渐形成最佳路由动态适应新节点的加入对节点、链路故障反应迟钝对拓扑稳定、小型网络适用目的节点接口距离………A左dn路由算法16动态路由中心路由（集中路由)213456中心路由计算机工作方式：

各个节点定期把自己的信道、相邻节点情况报告中心路由计算机，由计算机计算出各节点到其余节点的最佳路由，然后把路由表分发到各个节点上。特点：

最佳路由---理想路由信息上报、更新同步困难（特别是大网)路由算法17动态路由分布式路由

基本原理主动与其他节点交换路由信息－－路由协议节点独立计算最优路由－－分布式放弃全局最优、寻求局部最优化交换的信息越详细、交换的频率越快,路由优化越好,对网络带来的额外开销也越大。寻求在额外开销和反应速度间的平衡*可行性：分布计算能否统一？

最佳路由法则：（利用相同的信息，相同的算法)

若A认为到D的最佳路由要经过B，则B有相同的看法。

重18分布式路由分布式路由分析分布式路由的不利之处:利用部分路由信息，无法得到全局最优路由可能出现相互矛盾的路由反应快会造成路由震荡，反应慢则好处不大有利方面:局部范围，网络额外开销少可在局部获得最佳路由较准确，不需人工干预－－自动化重19分布式路由分布式路由算法要点交换路由信息分布式计算:最优路由计算方法哪些信息?交换方式边交换信息边计算可达、距离、费用、负载、延时……关20分布式路由常见的分布式路由:基于网络距离的分布式路由算法---矢量距离法基于信道状态的分布式路由算法---线路状态法重215.4.3距离矢量算法以中继节点个数为度量21345611111111交换路由信息13工作方式：每个节点自动找出相邻节点，形成初始路由表，距离为1每个节点定期和相邻节点交换路由信息－－路由及距离根据收到的路由信息，更新到其他节点的路径（最短距离)通过不断扩散，逐渐形成到所有节点的路由22距离矢量算法初始化,各节点形成各自的本地信息－－即邻接路由器扩散,各节点向邻居节点扩散已知的路由信息计算,各节点根据邻居节点扩散来的信息计算新的路由距离更新=到邻居节点的距离+邻居节点到目的节点的距离不断扩散,各节点定期不断向邻居扩散自己已知的路由信息213456112111111346532133311224444655对比23距离矢量算法目的节点下一节点距离221331信息发布者2目的节点距离113141节点1路由表更新初始值收到节点3路由信息目的节点下一节点距离221331更新后发布者3目的节点距离11214151收到节点2路由信息目的节点下一节点距离221331422距离更新=到邻居节点的距离+邻居节点到目的节点的距离更新后213456112111111422532关24距离矢量算法213456112111111目的节点下一节点距离221331422532节点1当前的路由表节点1向节点2发布的路由信息信息发布者1目的节点距离21314252节点1向节点3发布的路由信息信息发布者1目的节点距离21314252关25距离矢量算法213456112111111目的节点下一节点距离221331422532节点1路由表更新距离更新=到邻居节点的距离+邻居节点到目的节点的距离收到节点2路由信息发布者2目的节点距离1131415263目的节点下一节点距离221331422532更新后624发布者3目的节点距离1121415162目的节点下一节点距离221331422532更新后62433关26距离矢量算法交换信息节点所知的全网可达信息－－交换路由表（路由转发表)路由信息：目的＋距离（节点个数)

－－即通过“我”能到达哪些节点，有多远交换方式仅与相邻节点交换，定期交换与相邻路由器交换全网路由信息最佳路由计算方式每个节点告诉“我”的，都是他们的最佳路由。根据当前已知的，对比新知道的，算出最好的当前知道：到D经过C，总距离为5新了解到：B告诉“我”，经过他到D距离为2“我”到B的距离为2，

所以“我”到D的路由更新为：经过B到D，路由距离为4重27距离矢量算法几个相关问题如何交换路由信息何时?定期邻居失效/发现新邻居时和谁?邻居节点水平分割节点没有必要将从某节点收到的信息再传回给该节点无穷计数距离矢量算法会出现路由环路设计最大路径长度，以减轻环路出现时带来的损害用毒性反转方法，破坏路由环路28水平分割213456112111111目的节点下一节点距离221331422532节点1当前的路由表节点1向节点2发布的路由信息信息发布者1目的节点距离21314252节点1向节点3发布的路由信息信息发布者1目的节点距离21314252节点没有必要将从某节点收到的信息再传回给该节点29无穷计数在某种情况下,距离矢量算法可能出现路由环路,其现象是路由表项随路由信息更新,不断增加。

ACBD正常情况:A认为到D经过BC认为到D经过BB认为到D经过D路由环路:A认为到D经过BC认为到D经过AB认为到D经过C30ACBD平时:A收到C告知:D有两跳A收到B告知:D有一跳选BC收到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毒性反转－－解决路由环路213456112111111目的节点下一节点距离221331422532633节点1当前的路由表节点1向节点2发布的路由信息信息发布者1目的节点距离31425263节点1向节点3发布的路由信息信息发布者1目的节点距离21425263节点将从某节点收到的信息再传回给该节点时,告诉对方不能从我这里过无穷大无穷大无穷大扩32距离矢量算法特点:只与邻节点交换路由信息各节点独立计算最优路径能适应网络拓扑的变化稳定后，形成最短路径算法简单缺点:网络变化扩散到全网速度慢扩散时间:所有节点都发现变化的速度路由收敛慢收敛时间:大家分别计算，结果达到统一的速度存在路由环－－在网络变化未扩散完全时。

小网对比重335.4.4链路状态算法以线路的延时作为链路度量延时比节点数更能反映网络和信道的实际状况从发出PDU到收到应答来测量延时及变化线路的速率、当前负载节点处理能力---会影响延时能较好地防止网络拥塞现象、均匀分布网络流量工作方式：

从每个节点探询相邻节点，得到延时(链路状态)初始值

每个节点定期和所有节点交换路由信息－－探询的相邻节点链路质量

根据收集到的路由信息，计算到其他节点的路径（最小延时)重34链路状态算法213456435611421022交换链路质量—与全网的所有节点交换充实路由信息库－－"绘出”网络拓扑计算路由表来自1:A.B信息AB来自2:A、C.D信息来自3:B、C.E、F信息来自4:D.E、G、I信息来自5:F、G、I、J信息自己测得的I、JIJCDEFG测量链路质量66666对比35链路状态算法213456435611421022ABIJCDEFG发布者1序号时间2234422发布者2序号时间123146发布者3序号时间14214154发布者4序号时间122263151065发布者5序号时间3441063发布者6序号时间4553213456435611421022关36链路状态算法交换的信息与相邻路由器之间的链路质量（延时)交换方式与全网路由器之间交换－－有控制的泛射向全网路由器宣告相邻路由信息最佳路由的计算方法收集信息形成路由信息库利用最短路径算法计算路由－－以本节点为源当发现链路质量变化时，更新信息库看改变的路由对当前的各条最优路由是否造成影响，并更新重37链路状态算法几个相关问题如何测量线路开销如何发布链路状态分组如何计算最佳路由38链路状态算法如何测量线路开销利用echo分组的延时来评估是否计入载荷从开始排队算起?从开始发送算起?ABT39链路状态算法如何发布链路状态分组何时?定期链路状态发生改变时和谁?全网节点怎样才能和全网节点交换?洪泛，但是在相当的控制之下每条信息有序号，节点收到相同序号的信息就丢弃每条信息有发布时间，节点同时收到多条信息时，只处理时间较近的一条213456重40链路状态算法如何计算最佳路由最短路径算法－－Dijstra算法A1A2A4A3A526512151)初始化时，设A1到其它不直连顶点距离为∞寻找A1到所有节点的最短路径A2A3A4A5顶点距离路径2)选择距离最短的路径3)观察通过新选择的路径是否能更短到达其它顶点4)选择出的最短路径将不参加下一轮比较5)反复2-4步，直到不剩有顶点265∞A2A3A4A1A2A3－－3更新A1A2A33A1A2A4－－∞A1A2A5－－4A1A2A3A4－－4更新A1A2A3A44A1A2A3A5－－8A1A2A54A1A2A3A4A5－－∞更新难41链路状态算法最短路径算法的计算思想每一步都取出当前最短的路径,计算该路径对其它路径的改变从最近开始逐步计算到最远213456关42链路状态算法特点与全网节点交换路由信息－－路由信息的扩散各节点独立计算最优路径－－一致性、准确性有较好的保证不是建立在别人的计算结果上（如距离矢量算法)能适应网络拓扑的变化，稳定后能形成最短路径收敛速度快－－可在大网中使用不是计算之后再扩散算法复杂，存储空间需求大需要记录全网所有的链路状态对比重435.4.5分级路由体系网络规模大－－巨型网络建设结构、管理机构等众多网络结构复杂各自进行各自的路由网间设定网间的路由方式分级路由体系屏蔽网内路由细节考虑网间路由的一些管理性特点网间路由网内路由445.4.6一些特殊的路由问题广播数据的路由多点播送数据的路由移动主机的路由策略无线多跳网的路由技术45广播数据的路由广播数据－－需要发送给所有目的地的分组实现方法类型向每个目的发送一份拷贝洪泛多目的分组路由广播分组带有所有希望的目的路由器选择适当线路生成树按树的路径转发分组没有回路21345664656361626666666646多点播送路由选择多点播送小组生成树小组1的多点播送树小组2的多点播送树47多点播送路由选择播送树有源树组播组里,每个发送源都形成一颗组播树－－有源树组播路由器在转发数据时,根据分组源地址和相应的树表,决定转发的路径共享树－－核心基本树在组播组里,大家遵循同一颗组播树－－共享树组播源站先想办法将数据发送到共享树的根节点,由根节点再延着树转发数据减少树表所占空间组播树的形成－－协议11111源源1111根1扩48反向路径转发工作方式路由器收到组播分组时，在树表中查本机到达源地址所用的接口若收到分组的接口与查到的接口是一致的，则转发组播分组到树的其它接口，否则丢弃目标减少组播分组的转发个数基本思想:若源节点在树上，基本上可以放心转发，即不是环路上传过来的多点播送路由选择11111扩49组播标准组播地址IP组播地址：224.0.0.0~239.255.255.255（D类）MAC组播地址：0x0100.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移动主机的路由策略寻径与移动的矛盾节点的网络地址一般具有定位性当节点移动后,无法通过节点的地址对节点定位,也就无法将数据路由到节点。本地代理、外地代理本地代理AB外地代理x注册通知A在我这里A在x处51无线多跳网络的路由技术无线多跳网络－AdHoc网络特点拓扑复杂，多变，变化速度快路由技术先应式:表驱动式，先建立路由表反应式:按需路由，只有当需要时才去发现路由扩52其它路由算法负载分担路由协议边界路由协议昂贵的长途干线可节省535.4.7路由算法的应用网间路由（大型网络)链路状态算法网络拓扑结构复杂网间路由54路由算法的应用网间路由（中小型网络－－园区网)距离矢量算法简单RouterRouterRouter55路由算法的应用以太网桥中的路由:

洪泛路由+自学习路由565.5拥塞控制网络拥塞当节点阻塞时,将蔓延到全网,使网络吞吐能力下降网络流量过于集中,超过信道传输能力流量吞吐量理想网络流量过于集中,超过节点处理能力57拥塞一个点的拥塞会向全网蔓延关585.5.1拥塞控制与流量控制拥塞控制不同于流量控制控制对象不同流控:局部于两点之间拥控:全局控制，拥塞点－附近节点－全网范围控制结果不同流控:两点之间发送方降速拥控:拥塞点得到缓解控制方法不同流控:降低发送速度拥控:预分配资源，更改路径，丢弃分组等重59拥塞控制与流量控制拥塞控制与流量控制之间有联系,易混淆网络拥塞后,吞吐量下降,节点响应慢,感觉象对方收不下来,从而误判为需要流量控制流量控制的不好是造成拥塞的原因之一在拥塞控制机制中,可能用到流量控制手段但拥塞控制事关全局,仅在个别节点的个别链路上进行流量控制,并不能有效解决网络拥塞问题重605.5.2拥塞控制的基本方法预防和避免－－开环不使拥塞出现的方法缓冲