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

第五章

网络层1背景与相关问题2路由算法概述3路由算法4拥塞控制5网络互联11背景与相关问题1.1背景1.2网络层提供的服务1.3网络层的功能1.4网络层基础21.1背景链路层仅实现了数据单元(DU)在信道上的传输物理层链路层物理层链路层物理层MAC物理层MAC物理层MAC物理层MAC链路层将DU向某个/某些相连的站点传输物理层链路层物理层链路层形成网络的基础在上层，将DU再次传送出去，扩大DU的传输范围DU在一个设备内部实现链路层将DU向对方站点传输31.1背景由任意多个局域网和点对点链路的连接结构网络基本元素L1L2L1L2L1L2L1L2L3=点对点局域网(总线、环形、…)路由器在L3中继DU任意连接结构41.1背景简化模型“链路层”“物理层”“信道”简化成链路(线条)，DU从源站点的L3出发，经过中间多个L3的转发，最终到达目的站网络层的核心任务将分组从源端传送到目的端分组将如何穿越网络从源端到达目的端？相连端到端中间节点：如何知道目的地在何处？多条路径该选哪条路？选好的路故障怎么办？网络拥塞怎么办？★51.2网络层提供的功能★寻址标识节点，节点定位路由选择传播路径信息、形成路径选择路径存储转发接收数据并存储，并按选择的路由转发（逐段转发）拥塞控制网际互联穿越多个同构或异构网络可能涉及分段与重组记帐61.3网络层提供的服务★向传送层提供穿越网络的、端到端的服务，并屏蔽网络的具体细节向传送层提供的服务与具体的网络环境和技术无关传送层不必也不需要了解具体的网络情况对传送层而言，对等实体的通信就像直接通信一样服务类别面向连接的服务通常由面向连接的协议实现无连接的服务通常由无连接的协议实现71.3网络层提供的服务针对网络层究竟应该提供何种服务，两大阵营产生了激烈的冲突争论的焦点：通信子网应承担什么样的任务？面向连接还是面向无连接的服务和技术？以电信公司为代表认为网络层应提供面向连接的服务以IETF（Internet工程任务组）为代表认为网络层应提供无连接的服务81.3网络层提供的服务以电信公司为代表的理由100年来电信系统的成功经验就是典范，认为：通信子网应采用面向连接的服务与技术网络层应该提供可靠的服务尽量简单的终端建立连接后，通信更容易受到控制,可在连接上限制用户流量以IETF为代表的理由通信子网应采用无连接的服务与技术，因为：通信注定不可靠需要终端自行解决差错等问题－－复杂终端终端的复杂性与终端的成本不一定成比例上升用户不必支付过时的、高额的通信费用网络的适应性更强、带宽利用率更高更自由91.3网络层提供的服务两种不同的观念形成了两种不同的通信子网构成方式面向连接的通信子网——虚电路无连接的通信子网——数据报典型的面向连接的网络层ATM的网络层X.25网的网络层典型的无连接的网络层Internet的网络层★10数据报与虚电路虚电路方式节点寻径速度快数据报方式健壮性强重新建立连接，重新开始11数据报与虚电路项目类型数据报子网虚电路子网都是以分组为单位，存储转发、逐站寻径建链与拆链NOYES地址源、目地址虚电路号保存状态信息NOYES（虚电路映射表）路由选择每个分组独立选路所有分组沿已建好的路径转发节点或线路损毁的影响影响不大，可立即重新选路所有经过的虚电路被终止，须重新建立连接拥塞控制较难较易服务质量较难较易灵活性更好稍差★121.4网络层基础网络地址：编址与寻址路由表（FIT）：记录到达目的地的路径信息Routed：查表方法及转发策略Routing：计算到目的节点的最佳路径，生成并维护路由表网络层分组格式（PDU）网络层协议进一步分析无连接模式、连接模式★131.4.1网络地址网络地址的编址需求全网唯一地址：每个站点至少有一个唯一网络地址来标识网络地址结构有规律，有助于站点位置的查找（寻址）全网统一编址两个编址参考实例邮政编码6100xx6102xx6117xx郫县成都双流清水河校区沙河校区61830000832000008320111483201120832011198320345661830114618301196183012061834321电话号码特点：区域编址内部子区域编码任意编排特点：中心编址按中心接口位置编排141.4.1网络地址电话网（中心编址）国家号+城市号+局号+终端号Internet（区域编址）网络号+子网号+主机号对比以太网MAC地址编码MAC地址：xx-xx-xx-xx-xx-xxIP地址：aaa.bbb.ccc.ddd平面地址，地址与站点位置无关结构地址，地址与站点位置相关：位置在某个网络(aaa.bbb.ccc.0)区域内结构地址为网络协议提供了寻找站点所在位置的部分线索，但这对于寻找网络站点还远远不够！151.4.1网络地址考虑站点A向站点B传递报文ABR1R2R3R4R5传递过程可以分解为：1、A将报文传递到R1上2、R1设法找到B所在的区域位置(R5),并寻找到R5的路径，沿路径传递报文3、R5将报文传递到B上寻址的关键点：是各个R如何找出目的R在何处、及确定传输路径的问题，与源网络或目的网络关系不大。(中心编址方案亦如此)161.4.1网络编址和寻址区域编址与中心编址方案的寻址差异区域编址可能有多个目的R带来寻址灵活性的同时，也带来了寻址计算的复杂性中心编址只仅有一个目的R寻址方式简便、单一171.4.2路由表与转发策略★路由表（RoutingTable）通过路由协议计算出某个节点到目的节点的最佳路由，形成的路径信息有时也与转发表同义（ForwardingTable-FIT）注意：有时分为路由信息表和转发表两种表，而转发表由路由信息表得到路由表的组成ABCED121122A节点的路由表目的下一站出口度量B直连21DC13……181.4.2路由表与转发策略转发策略查路由表（转发表），根据转发路径进行转发转发之前如何查表？最短适配：从高地址部分开始适配即从最大的范围开始例：8602861830328最长适配：从低地址部分开始适配即从最接近主机的路由开始例：202.115.12.0高地址－－网络号低地址－－主机号其它查找算法：顺序、折半、Hash……不考虑地址的结构性，可提高查找效率与以上两种方法配合以提高效率完整适配：要求路由表规模太大，一般不用191.4.2路由表与转发策略主要技术问题(按地址寻址方式)地址空间太大，每个节点都装不下IP地址：32bit（232个地址）IPv6地址：128bit（2128个地址）只能记录已知部分查表运算量太大如上万个站点的表IP协议的处理方法仅考虑网络号部分，忽略主机号部分可以大大减小转发表项数目但仍然还有很大的运算量目的子网下一节点出口链路子网号主机号IP地址32比特201.4.3路由选择（Routing）寻找各处站点，在本地建立路径的方向转发表(FIT）Routing协议设置路由信息211.4.3路由选择（Routing）每个站点的FIT表内容表示从自己出发达到任意目的地址的“最短路径”。(不同站点FIT内容不同)Routing协议站点间路由信息交互计算到任意站点的最短路由，生成FIT表的内容221.4.4网络层分组格式L3转发DU—微观问题需要在DU中携带转发信息，L3才能处理L3接收DU、寻找路径、转发DU功能构成L3协议定义协议数据格式(分组，Packet)DU=网络层Packet=[协议首部+Data_Block]协议首部={类型、状态、方向等信息}Data-Block=携带的数据块(若干字节数据)HDataDU网络层分组链路层DU链路层HData根据首部信息选择转发出口链路L3231.4.4网络层分组格式无连接模式分组标志：首部包含源地址和目的地址连接模式分组标志：首部包含流ID号(可能名称不同)VerHLenTOSTotalLengthIdentifierFlagsFragOffsetTTLProtocolHCSSourceIPAddressDestinationIPAddressDataBlockIP分组格式GPILGNLCN分组类型DataBlockX.25分组格式(源地址、目的地址)(逻辑信道号=流ID)241.4.5网络层协议—进一步分析两种典型的网络通信体制比较无连接模式(ConnectionlessMode)通信体制数据报(Datagram)通信连接模式(ConnectionMode)通信体制虚电路(VirtualCircuit)通信S1D1D2S2考察S1D1、S2D2两对通信25无连接模式典型特征PDU首部包含有源地址S和目的地址D中间节点用目的地址D寻找PDU转发方向S1D1D2S2HDataSD……报文常规传输路径报文即使走错，地址D也会指出正确方向特性：1、不需要为通信预先建立完整传输路径2、报文没有固定的传输路径(数据报通信体制)3、各个报文独立穿越网络4、网状结构下，部分节点或链路故障不会造成通信中断5、节点难以估计通信自己的通信流量26连接模式典型特征PDU首部用连接id标明中继方向需要事先建立连接id的中继关系S1D1D2S2报文常规传输路径报文走错，连接id将把报文送到错误方位HDataid……11①②①②①②①②①②⑤①②③②⑤①27连接模式连接id标识的传输路径逻辑上等效于一条传输电路(VirtualCircuit)S1D1D2S211①②n连接id的编号空间大小等同于该链路的虚电路数目特性：1、需要预先建立id转发的完整传输路径2、报文沿id标识的固定路径传输(虚电路传输体制)3、同源、同id的各个报文沿路径顺序传输4、传输路径上节点或链路故障将造成通信中断5、节点可估计通过自己的通信流量12n28网络层协议—进一步分析DU传输路径问题HData转发信息=目的地址根据地址选择出口链路到X，走AA到X，走C到X，走QQX123njkm12knjkm12injkmHData原始转发信息13HDataHDataHDatamk根据首部的不同ID，从同一源站点发出的分组将走不同的路径，同时，分组首部ID也随之改变根据首部不同目的地址，从同一源站点发出的分组将走不同的路径，分组首部不发生改变HDataC29网络层协议—进一步分析无连接vs连接

FITConnectionless网络协议利用FIT表直接转发PDU尽量发挥FIT直接转发的优势：1、用于网状拓扑结构的网络中2、动态修改FIT，形成动态路由，以适应网络动态变化3、地址空间巨大，每个报文都需经FIT查表，CPU计算负担重FITConnection网络协议FIT表仅用于建立id之间的转发关系FIT和id双重处理，尽量降低FIT处理负担：1、采用简单拓扑结构(如树形结构)2、不考虑网络动态变化，固定FIT3、优化数据转发：连接报文数目<<数据报文数目4、id转发关系动态建立，一次建立多次使用5、链路id空间小，查表负担轻30查表算法目的子网下一中继出接口FIT表路由器有一个FIT表供路由查询FIT可能达到几千上万条表项，假设有10000条表项，对每个PDU的目的地址平均需要查询5000次表项假设路由器每秒可转发M个报文，表项查询速率将达到5000*M

（表项/秒）连接id对接表连接id出id出接口每个接口有一个连接id对接表，其表项只有几千个接口收到PDU，根据PDU的id号(=a)查表转发时，直接采取表索引找到出id和出接口。id=连接id对接表[a].出id

接口=连接id对接表[a].出接口31通信体制：小结无连接方式A-B的通信可随时切换传输路径具备抗链路或中继站点故障能力分组到达B的顺序可能发生与A发出的顺序不一致易于实现广播通信中继转发性能较弱(地址空间大，FIT表庞大)每个分组平均需要M/2次查表(M为表项数)面向连接方式A-B的通信沿固定路径传输不具备抗链路或中继站点故障能力分组按顺序传输难以实现广播通信中继转发能力强(只关注流经本站的ID，FIT表小巧)优化情况下，每个分组只需一次查表32★2路由算法概述★2.1路由的基本概念2.2路由算法的要求2.3路由最优化原则2.4路由算法分类332.1路由的概念路由的基本概念源到目的节点之间，由节点和线路组成的一条通路路由选择面临的问题存在多条路径选择一条最优路径：如何选择？节点需掌握所有的路径：表项规模？最优路径随网络拓扑变化而变化路由需要及时更新，但要避免路由振荡避免出现路由环路.避免网络阻塞负载均担？★34路由相关问题拓扑结构变化引起网络中多条路径发生改变，需要及时根据变化，进行路由调整X信道故障节点故障新节点加入35路由相关问题路由环路节点间路由配合不当，可能出现路由环路PDU进入环路后，再也出不来了36路由不一致性路由信息分发时延会造成路由的不一致问题要求所有节点同时掌握各种情况是不现实的故障正常路由链路故障后的一段时间内37网络流量过于集中，超过信道传输能力网络流量过于集中，超过节点处理能力路由相关问题网络拥塞路由过分集中到网络中的某些局部区域后果：拥塞逐渐蔓延到全网，网络吞吐能力下降流量吞吐量理想382.2路由选择算法的要求正确性：目的地存在且可达简单性：计算简单，实现容易健壮性：路由算法能适应节点故障、增减造成的拓扑结构的变化，及时调整路由，并不影响全网工作稳定性：路由更新后会有过渡期，路由算法应使过渡期尽量短，具有快的收敛性（避免路由震荡）公平性：节点地位平等最优化：一定策略下的最优（有时也称策略性）低开销：路由控制信息尽可能少，开销尽可能低。★392.3最佳路由什么是最优路径？源、目节点间存在多条路径1到5的路径有多条：1-2-5，1-3-5，1-4-5，1-2-3-5……寻求一条最优路径，需求不同会有不同的最优路径最优定义以距离为度量：最短距离以跳数为度量：最少节点数以时延为度量：最小延时以投递率为度量：最大成功率以带宽为度量：最大吞吐量……实际网络中，可能考虑一项，也可能需要考虑多项参数，进行选择通常称这些度量参数为Cost或Metric★25314402.3最佳路由最佳路径节点si到节点sj的所有路径P={1,2,…}中，若则称为si到sj的最佳路径，其距离为即：所有路径中最短的一条为最佳路径SD2323431311找出S到D的最佳路径R1R2R3R4R541最佳路径—例从A到E的多种最佳路径ABCDE若考虑经过最少中间节点，则最佳路径为A-D-E10Mbps10Mbps10Mbps100Mbps100Mbps100Mbps结合信道速率若考虑选择路径传输容量，则最佳路径为A-B-C-E信道占用率40%80%30%10%15%12%若考虑路径可用速率，则最佳路径仍为A-B-C-E若考虑路径有较小传输延迟，则最佳路径为A-B-D-E(80%占用率会大大增加传输延迟)42路由选择的最优化原则最优化原理若I到K的最佳路径经过J，则lm这条路径也是J到K的最优路径证明(反证法)若J到K的最佳路径是另一条，假设经过l1和l2，而不经过lm则必有D(l1)+D(l2)<D(lm)可以得到：D(ln)+D(l1)+D(l2)<D(ln)+D(lm)与{ln，lm}为I到K的最佳路径矛盾IJKl1l2lmln43路由选择的最优化原则用途当I计算最优路由后将分组交给J，J所选择的最优路由与I选择的是一致的！是存储转发、逐站寻径的基础，是分布式路由算法的基础推论1某站点到目的节点K的最优路径，只需知道该节点到邻居节点的“距离”和邻居节点到K的最优路径。K哪条最优？d1d2d3abca+d1b+d2c+d344汇集树（SinkTree）推论2从所有的源到一个指定目标的最优路径的集合构成了一颗以目标节点为根的树。从一个源到所有目标的最优路径的集合构成了一颗以源节点为根的树路由算法为所有路由器找到并使用汇集树452.4路由算法的类型及特点静态路由算法（非自适应算法）路由表内容不随网络的变化而变化算法简单，可靠性高，但不灵活，适用于小型网络动态路由算法（自适应算法）根据网络的变化计算路由路由表内容随网络的变化自动更新动态路由需在节点间交换信息算法较复杂，但更能反映网络实际情况适用于网络拓扑变化、大型网络46★2.4.1几种静态路由算法固定路由算法事先计算所有节点的最佳路径，形成中心路由表。各节点根据中心路由表，形成自己的路由转发表洪泛法（扩散法）节点将收到的分组沿本节点各出线（收分组的线除外）转发出去，总有一条路径最优随机路由节点将收到的分组根据概率随机选取一个出口将分组转发出去烫土豆法节点将收到的分组尽快出手，选择队列最短的出口转发472.4.2几种动态路由算法涉及的问题节点之间交换路由信息快速适应拓扑变化感知拓扑变化快速传递变化信息快速形成新的稳定的路由（无环路、不震荡，快速收敛）中心路由算法逆向学习法分布式路由算法（重点）距离矢量法、链路状态法48中心路由算法（集中路由）原理各个节点定期将本节点及其与相邻节点的信息报告给中心路由计算机由中心路由计算机计算出各节点到其它节点的最佳路由，然后分配到各个节点特点理论上可得到全网最优路由（考虑了流量等全网信息）但实现困难，很难在大网中使用，适应于小网，原因：信息上传困难同步困难路由更新过时21345中心路由计算机★49逆向（反向）学习法原理根据接收分组中的源地址和接收端口号，形成转发表，以便下次作为目的节点时的转发路径特点能动态适应新节点的加入对线路故障、节点损坏反应迟钝适应拓扑结构相对稳定、小网CA收到从A送来的分组路由表中记录从该接口可以到达A★目标节点端口距离………………AnDn50分布式动态路由算法基本原理节点之间需相互交换路由信息节点单独计算路由基本特点局部最优，全局不一定最优相互交换信息越具体、越频繁，路由优化越好，但造成的额外开销也越大。需要在额外开销和路由更新的频率之间进行折中优点动态反映网络变化，路由表自动形成与更新（不需人工干预）局部最优，路由开销少缺点局部最优路由，不是全局最优路由可能出现不一致（矛盾）的路由可能出现路由震荡（路由表变化太快）可能出现路由发散（不能收敛）★51分布式路由算法要点交换路由信息：分布式计算：节点根据交换的路由信息，采用最优路由计算方法计算最佳路由哪些信息？与谁交换？边交换信息边计算可达、距离、费用、负载、延时……与邻居、与所有节点何时交换？定时、拓扑变化时★523路由算法3.1洪泛路由（扩散法）3.2距离矢量路由3.3链路状态路由3.4分级路由3.5一些特殊的路由533路由算法2312R0R1R2R3R4路由信息：链路或路径距离、节点间连接关系等信息信息交互：节点间交换路由信息的方法路由算法：计算到其余节点的路径的算法计算到所有已知路由节点的最佳路径通过交换，积累关于网络的更全面的路由信息关于路径计算所需的参数节点初始条件1、掌握到各邻居节点的链路及距离2、能感知链路的状态(正常、故障)路由算法1、若节点什么都不知道，洪泛路由算法2、若知道邻居节点到各处的最佳路由—距离矢量路由算法3、若知道各节点的链路连接状态—链路状态路由算法543路由算法R0R1R2R3R4洪泛路由：入报文向所有方向转发出去，总有报文到达目的地R0R1R2R3R4距离矢量路由：如果所有邻居都已形成到其余节点的最佳路径，则R0汇集整理，就可形成自己到各处的最佳路径汇集路由信息R0链路状态路由：如果收集到所有节点的链路连接状态，R0就能形成网络的拓扑结构，并能计算出到各处的路由Ri的链路连接状态RjRkR0最佳路径结果=FIT表内容目的1:下一跳为Ri，距离为x目的2：下一跳为Rx，距离为y最佳路径中只取了下一跳553.1洪泛路由(FloodingRoute)★节点将收到的分组向所有方向扩散（接收链路除外）S发送两份拷贝R1、R2分别发送两份拷贝R3发送3分拷贝特点无需掌握网络的拓扑结构节点无需建立FIT表分组肯定能到达目的节点高度稳健性目的节点会收到多个重复分组所有节点都能收到信息特别适用于广播SDR1R2R356洪泛路由—分组泛滥问题如果网络拓扑存在环路，且没有分组抑制措施分组将会在网络上无限循环转发可能会出现扩散风暴，造成网络的过载而瘫痪T0时刻T1时刻T2时刻T3时刻T4时刻假设：源节点不扩散自己发送的分组目的节点不扩散自己接收的分组上一时刻分组当前时刻分组57洪泛路由—分组抑制抑制约束条件节点不可能根据分组内容判断两个分组是否相同节点不能用地址判断两个分组是否相同抑制方法1：跳数抑制法(限制分组转发次数)在分组中，设置跳数计数值设置生命周期（TimeToLive，TTL）初始值为目的站点最大估计跳数值节点转发分组前，将跳数计数减一，不为零继续转发，为零则停止转发，并丢弃。T0时刻,TTL=4T4时刻，该分组消失58洪泛路由—分组抑制抑制方法2：唯一分组标识法(转发过的不再转发)源站点为所有发送的报文统一编排序号分组标识：<源地址，序号>在全网范围内是唯一的节点记录已经转发过分组的标识：<源地址,序号>需定期清除记录，以免占用大量存储空间转发前，节点识别分组标识，抑制转发过的分组T1时刻T0时刻T2时刻,中间节点只转发1次59洪泛路由—小结不需要掌握网络拓扑结构、不需要FIT表分组总能到达目的节点(除非脱离了网络)目的节点可能收到多个相同分组若不抑制分组扩散，网络将瘫痪树形拓扑除外跳数抑制法比唯一分组标识法占用更多网络资源跳数法是无状态的唯一分组标识法是有状态的(与转发历史有关)节点需记录：转发过的节点地址、最新序号60洪泛路由的应用军用网节点随时都有被毁的可能，此路由算法可最大限度地将信息传输到目的地MANET节点可自由移动，网络拓扑结构随时都在发生变化。按需路由（如AODV）用洪泛路由找到目的节点后，再建立传输路径MobileAdhocNETwork613.2距离矢量路由★原理：考察如图网络拓扑结构及各条链路的距离R1到D的最短距离为4R2到D的最短距离为3R3到D的最短距离为5S根据R1、R2、R3的信息推算到D的最短距离S到D的距离=S到邻居i的距离+邻居i到D的距离(距离矢量)算法思想S获知各邻居到D的最短距离找出S到D的最短距离和下一跳中继节点SD2323431311R1R2R3R4R5DR55DR53DR24D4D3D5R1：R2：R3：+132=567DR1562距离矢量路由—DV协议初始阶段每个节点形成从自己到邻居节点的矢量路由信息矢量路由信息={[目的,下一跳，距离],[…]}SD2323431311R1R2R3R4R5R1R11R2R23R3R32SS1R2R21R4R43SS2R5R53SS3R1R11R4R44R5R51………………………63距离矢量路由—DV协议路由信息扩散每个节点把自己的路由信息形成分组向邻居扩散扩散内容为{[目的,距离],[目的,距离],[…]}SD2323431311R1R2R3R4R5S1R21R43S2R53S3R11R44R51………………………S1R21R43R1S3R11R44R51R2S2R53R3R1R11R2R23R3R32SR12R2R12R4R141+(R1)SR26R1R24R4R27R5R243+(R2)S原有SR34R5R352+(R3)………64距离矢量路由—DV协议用收到的信息更新自己的路由信息S收到Ri的路由信息后，更新路由信息的过程出现新的目的地址，S增加一条路由有相同路由，比较已有的短，还是经Ri的短，选择更短的D(S,Rx)>D(S,Ri)+D(Ri,Rx)?例：用R1的路由信息更新时D(S,R2)=3经R1到R2的距离为D(S,R1)+D(R1,R2)=1+1=2R1R11R2R23R3R32S原有的路由信息S1R21R43R1R1R11R2R12R3R32R4R14S更新后路由信息S3R11R44R51R1R11R2R12R3R32R4R14R5R24R2S更新后路由信息S2R53R3更新到R2的路由增加到R4的路由增加到R5的路由R1R11R2R12R3R32R4R14R5R24无更新65距离矢量路由目的节点下一节点距离221331信息发布者2目的节点距离113141节点1路由表初始值收到节点3路由信息目的节点下一节点距离221331更新后发布者3目的节点距离11214151收到节点2路由信息目的节点下一节点距离221331422距离更新=到邻居节点的距离+邻居节点到目的节点的距离更新后213456112111111422532关66距离矢量路由213456112111111目的节点下一节点距离221331422532节点1当前的路由表节点1向节点2发布的路由信息信息发布者1目的节点距离21314252节点1向节点3发布的路由信息信息发布者1目的节点距离21314252关67距离矢量路由213456112111111目的节点下一节点距离221331422532节点1路由表更新距离更新=到邻居节点的距离+邻居节点到目的节点的距离收到节点2路由信息发布者2目的节点距离1131415263目的节点下一节点距离221331422532更新后624发布者3目的节点距离1121415162目的节点下一节点距离221331422532更新后62433关68距离矢量路由路由信息周期性地逐跳扩散，周期性更新经过若干周期后，每个节点都掌握到任意节点的最短路由R1R11R2R12R3R32R4R14R5R24周期i扩散更新R1R11R2R12R3R32R4R14R5R24………周期i+1扩散第0周期：掌握到1跳节点的路由第1周期：掌握到2跳节点的路由第2周期：掌握到3跳节点的路由…69距离矢量路由路由信息的维护如果新的路由与旧的路由距离相同，选择哪一条？维持原有路由不变(稳定传输路径考虑)若某条路由长时间没有刷新，将被删除重复的路由信息(距离相同、源于周期性扩散)用于刷新路由表项的生命期70DV协议的改进DV协议的主要问题：无穷计算问题没有让某条不存在的路由从所有节点中消失的机制！设计最大路径长度（跳数），以减轻环路出现时带来的损害R1R2R3R4111到R1的距离123R1到R2链路中断后323消失消失4消失5消失6消失5到R1的距离变化71无穷计数问题算法的缺陷：对好消息反应迅速，对坏消息反应迟钝72DV协议的改进改进1：水平分割不处理回传的路由信息（或者节点不将从某节点收到的信息再传回给该节点）例：R1处理从S传来的路由信息时回到刚才的例子R1R11R2R12R3R32R4R14R5R24R1根据路由信息形成的方式，下一跳为R1的表项显然是从R1产生的，因此：R1不处理表项中下一跳为R1的内容，从而杜绝信息的回传R1R2R3R4111到R1的距离123R1到R2链路中断后消失消失(不处理)3消失消失消失(不处理)R1R2R3R41111水平分割失效的情形73ACBD当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，距离为五跳出现路由环路，并计数到无穷大网络拓扑存在环路时，水平分割失效74DV协议的改进改进2：毒性逆转发现链路断开(路由消失),由原来的悄然删除，改为向外扩散“距离无穷大”的路由(通知路由消失)节点将从某节点收到的信息再传回给该节点时，距离置为无穷大，告诉对方不能从我这过改进3：触发更新收到路由信息有距离无穷大路由项，直接更新对应的路由表项(不再用距离判定是否更新)改进4：更新抑制当路由项的距离更新为无穷时，不是删除它，而是保留一段时间不更新，直到该信息传遍整个网络75距离矢量路由—小节特点：只与邻节点交换路由信息各节点独立计算最优路径（但依赖邻居的计算结果）能适应网络拓扑的变化，稳定后，形成最短路径算法简单缺点：交换路由信息分组长度分组长度与路由表项数量成正比网络变化扩散到全网速度慢扩散速度：所有节点都发现变化的速度路由收敛慢收敛速度：大家分别计算，结果达到统一的速度当拓扑结构、距离参数变化频繁时，算法可能不收敛存在路由环－－在网络变化未扩散完全时。实用协议：RIP适合于变化较慢的小网★76DV协议—实验实验者工作在网络的某个节点上直连节点为该节点的邻居节点实验内容1、根据邻居节点信息形成路由表2、形成路由信息向各邻居扩散3、根据接收路由信息更新路由表4、重复(2、3)，直到路由表稳定不变EBCDF本节点收到路由信息形成路由表发送路由信息定期考查点：如何更新路由表考查点：如何形成路由信息应该向谁发送初始状态考查点：如何形成路由表773.3链路状态路由★回顾：DV协议路由算法累积型最佳路由计算D(S,D)=min(D(S,R(i))+D(R(i),D))R(i)∈{S的邻居节点}从邻居的最佳路由累积而成路由状态变化时，需要很长时间才能(收敛)稳定DV协议收敛慢的原因分析累积型路由计算等待邻居计算出最佳路由之后，才能计算出自己的最佳路由协议算法实现邻居间相互依赖和相互等待结果，导致周期性更新动作78链路状态路由如何避免等待邻居的计算结果？掌握其它节点(不限于邻居)的链路状态信息不依赖其它节点的计算结果链路状态路由算法思想若节点能收集到网络上所有链路的状态信息链路状态：链路两端的节点、链路的距离可重构网络的拓扑结构进而可独立计算到任意节点的最佳路由最短路径优先(SPF，ShortestPathFirst)链路状态路由协议（LS或SPF）：收集所有链路状态信息重构网络拓扑结构计算自己到任意节点最佳路由形成到下一跳的FIT表链路状态改变链路状态路由节点间信息交互79重构网络拓扑网络链路连接矩阵FAHK242B4D3G2E3O5L2从F节点重构网络原网络2ABCDEIHGLFKNOMJ552245322321224232311252180Dijkstra最短路径算法对任意网络拓扑结构，从任意一点出发到其余所有点最短路径的计算方法便于计算机处理的经典算法已找到最短路径的节点正处理的节点未处理的节点出发节点S到S距离最短的节点K第i步KK的邻居S0S1S2重复第i步，直到S2为空、S1为空81Dijkstra算法步骤设：源节点为F第一步：以F为起始，向所有可能路径前进一步FHK242AABCDEIHGLFKNOMJ5522453223212242323112521S0={F}S1={A,H,K}S2={…}82Dijkstra最短路径算法第二步：在已有路径中选择最短的继续前进图中的A和KFHK242B4D3G2L2AABCDEIHGLFKNOMJ5522453223212242323112521S0={F,A,K}S1={H,B,D,G,L}S0={F}S1={A,H,K}A,KA(B,D,G)K(L)83Dijkstra最短路径算法重复第二步在已有路径中选择最短的继续前进路径出现闭合点D、G、H处理：删除闭合点到F的距离长的一条(图中虚线)FHK242B4D3G2L2AABCDEIHGLFKNOMJ55224532232122423231125211M22E3O5S0={F,A,K,H,G,L}S1={B,D,E,O,M}84Dijkstra最短路径算法重复第二步在已有路径中选择最短的继续前进注意：G已没有后续路径可用(不在考虑之列)同样，删除闭合点的一条长路径FHK242B4D3G2L2AM2E3O5I22ABCDEIHGLFKNOMJ552245322321224232311252185Dijkstra最短路径算法重复第二步在已有路径中选择最短的继续前进同样，删除闭合点的一条长路径FHK242B4D3G2L2AM2E3O5I2C155N4ABCDEIHGLFKNOMJ552245322321224232311252186Dijkstra最短路径算法重复第二步在已有路径中选择最短的继续前进同样，删除闭合点的一条长路径(注意B-C)FHK242B4D3G2L2AM2E3O5I2C5N42J23ABCDEIHGLFKNOMJ552245322321224232311252187Dijkstra最短路径算法重复第二步在已有路径中选择最短的一条继续前进同样，删除闭合点的长路径FHK242B4D3G2L2AM2E3O5I2CN42J2ABCDEIHGLFKNOMJ55224532232122423231125213188Dijkstra最短路径算法到达最后一个节点，无链路可前行—完成计算形成从F到所有节点的最短路径FHK242B4D3G2L2AM2E3O5I2CN42J2ABCDEIHGLFKNOMJ5522453223212242323112521Dijkstra算法总结：让短路径传输的“更远”89Dijkstra最短路径算法AtoD最短路径发现过程临时性标注永久性标注90形成FIT表F的FIT表F计算出全部最短到所有节点，最终以A、H、K之一作为下一跳ABCDEIHGLFKNOMJ5522453223212242323112521AABACADAEHGAHHIAJAKKLKMKNKOH目的下一跳91链路状态路由协议目标节点间信息交互，获得全网所有链路信息协议操作内容链路状态维护(感知“通”或“断”)定时的Hello报文沟通测量链路“距离”延时、排队长度、信道速率、节点负载等参数“距离”

=1个或多个参数的组