《数据通信与计算机网络08分组交换》由会员分享，可在线阅读，更多相关《数据通信与计算机网络08分组交换（34页珍藏版）》请在金锄头文库上搜索。
1、第8讲 分组交换与路由选择第第8 8讲讲 分组交换与路由选择分组交换与路由选择 课时授课计划 课 程 内 容1第8讲 分组交换与路由选择内容： 电路交换和分组交换 虚电路和数据报 路由选择策略 目的与要求： 掌握电路交换和分组交换的基本工作原理； 掌握网络提供的服务方式：虚电路和数据报服务； 理解路由选择算法； 重点与难点： 重点：分组交换的工作原理、路由选择算法； 难点：路由选择算法。2第8讲 分组交换与路由选择课堂讨论：分组交换的工作原理？ 网络层提供的基本服务之一：路由选择？ 现代教学方法与手段： 投影 PowerPoint幻灯课件复习（提问）： IEEE 体系结构？ CSMA/CD和T
2、oken ring？3第8讲 分组交换与路由选择第第5 5章章 网络层网络层5.1 电路交换和分组交换5.2 虚电路和数据报5.3 路由选择4第8讲 分组交换与路由选择网络层网络层讨论：讨论：为什么需要网络层？为什么需要网络层？网络层提供哪些服务网络层提供哪些服务? 为什么网络互连中需要路由为什么网络互连中需要路由器等路由设备？器等路由设备？5第8讲 分组交换与路由选择OSI/RM Application protocolRepresentation protocol Session protocol Transport protocolAPDUPPDUFrameBitsPacketSPDUS
3、egment6第8讲 分组交换与路由选择为什么需要网络层为什么需要网络层主机主机A主机主机B结点结点 1结点结点 2结点结点 3网络连接网络连接数据链路连接数据链路连接数据链路连接数据链路连接 传输层传输层数据链路层数据链路层网络层网络层网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节，如子网网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节，如子网类型、拓扑结构、子网数目，向上层提供一致的服务、统一的地址类型、拓扑结构、子网数目，向上层提供一致的服务、统一的地址7第8讲 分组交换与路由选择交换通信网的数据交换通信网的数据交换方式交换方式电路交换（circuit switchin
4、g ）分组交换（packet switching）8第8讲 分组交换与路由选择电路交换电路交换电路交换的数据传输过程电路的建立数据传输电路释放电路交换的特点：时延小，适合于实时性强的交互式通信；对突发性通信不适应，信道利用率低；不具备存储数据或差错控制能力9第8讲 分组交换与路由选择电路交换电路交换12345DTEDCEDCEDTEDCEDCEDCEDCEDTEDTEDTE6ABCDE返回10第8讲 分组交换与路由选择分组交分组交换换分组交换的数据传输过程仍基于存储转发原理，但对数据传输单位的作了划分：将长报文或大的数据块分割成小段，为每小段附上地址、分组编号、校验等信息构成一个数据分组（数据
5、包），作为存储转发的逻辑数据单元。电路交换的特点：固定大小的分组单位较小，可充分利用线路空闲，从而减少了传输延时；出错重传的数据量也大大减少11第8讲 分组交换与路由选择分组交分组交换换虚电路（Virtual Circuit）数据报（ Datagram ）ACBDEACDH1H2H4H3H5H6ACBDEACDH1H2H4H3H5H6(a) 数据报服务数据报服务(b) 虚电路服务虚电路服务12第8讲 分组交换与路由选择虚电路虚电路含义： 通信子网借以实现面向连接服务的工作方式，通信子网借以实现面向连接服务的工作方式，需要源与目标之间建立一条逻辑上的通信链路。需要源与目标之间建立一条逻辑上的通信
6、链路。 涉及虚电路逻辑连接的三个阶段： 虚电路对立虚电路对立数据传输数据传输虚电路拆除虚电路拆除 在建立连接时，将从源端机器到目标机器的路由作为连接建立的一部分加以保存。在虚电路上传送的分组总是取相同的路径（路由）通过通信子网。13第8讲 分组交换与路由选择虚电路虚电路AEDCBH2H3H1H4H5依次建立依次建立5条条VC：VC1：A-B-EVC2：A-B-DVC3：B-D-EVC4：C-E-DVC5：A-B-C-D 入口入口出口出口H1H1H1125012B 012BB 入口入口出口出口AAH2 3010E001DD 入口入口出口出口BBE010H4001EH4 入口入口出口出口H3B40
7、00E002D 入口入口出口出口BDC000H5010D A B C D EA2C 0H5CH4虚电路路由表建立过程示例14第8讲 分组交换与路由选择虚电路虚电路特点：特点：包传输路径相同，不需要源地址与目标地址信包传输路径相同，不需要源地址与目标地址信息息 。 除了建立连接时需要路由，在数据传送过程中除了建立连接时需要路由，在数据传送过程中不需要作路由，无路由信息，只有虚电路连接不需要作路由，无路由信息，只有虚电路连接信息。信息。包的传输不会出现丢失、重复和乱序现象。包的传输不会出现丢失、重复和乱序现象。分类：分类：永久虚电路（永久虚电路（PVC）呼叫虚电路（呼叫虚电路（SVC）15第8讲
8、分组交换与路由选择数据报数据报通信子网借以实现面向无连接服务的工通信子网借以实现面向无连接服务的工作方式作方式 。为每个分组选择独立的路由，即不为每个分组选择独立的路由，即不同的分组可以走不同的路由。同的分组可以走不同的路由。16第8讲 分组交换与路由选择数据报数据报AEDCBH2H3H1H4H512目的站目的站输出线输出线BCDE1212结点结点A的的路由表路由表数据报的路由表数据报的路由表每个分组都需要携带完整的目的地址。每个结点保存一个到网内其他每个分组都需要携带完整的目的地址。每个结点保存一个到网内其他结点的输出线选择表结点的输出线选择表17第8讲 分组交换与路由选择虚电路与数据报的比
9、较数据报子网虚电路子网延时分组传播延时电路建立，分组传输延时路由选择每个分组单独选择路由建立虚电路时选择路由，以后所有分组都是用该路由状态信息子网无需保存状态信息每个节点要保存一张路由表地址每个分组包括源端和目的端的完整地址每个分组含有一个短的虚电路号节点失败的影响除了在崩溃时正在由该节点处理的分组都丢失外，无其它影响所有经过失败节点的虚电路都要被终止拥塞控制难如果有足够的缓冲区分配给已经建立的虚电路，则容易控制18第8讲 分组交换与路由选择路由选择路由选择理想路由算法的基本特性正确性（正确性（Correctness）简单性（简单性（Simplicity）健壮性（健壮性（robustness）
10、稳定性（稳定性（stability）公平性（公平性（fairness）优越性（优越性（optimality）高效性（高效性（efficiency）19第8讲 分组交换与路由选择路由选择路由选择静态路由策略扩散法固定路由选择随机路由选择基于流量的路由选择动态路由策略在网络互联中讲解20第8讲 分组交换与路由选择扩散法扩散法( (洪泛洪泛) )基本思想把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。主要问题洪泛要产生大量重复包。解决措施每个包头包含站点计数器， 每经过一站计数器减1， 为0时则丢弃该包；记录包经过的路径AKLPEMNDCB图图 洪泛算法示意图洪泛算法示意图信源信源21第
11、8讲 分组交换与路由选择扩散法扩散法( (洪泛洪泛) )选择性洪泛算法（selective flooding）洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况路由器和线路的资源过于浪费，实际很少直接采用；具有极好的健壮性，可用于军事应用；作为衡量标准评价其它路由算法。22第8讲 分组交换与路由选择固定路由选择固定路由选择固定路由选择 在每个节点上保持一张路由表,表上标明对每一个目的地址应走哪条链路进行转发.路由表是在整个系统进行配置时生成的.配置时根据事先计算好的“网络中任意两个节点之间最短路径”,将这些最短通路制成路由表,存放在各个节点中.每一个分组都可在所到达的节点
12、中查找下一步应转发到哪一个节点(下一站节点或后继节点). 经典的求最短路径算法是Dijkstra算法.它的条件是已它的条件是已知网络的拓扑和各链路长度知网络的拓扑和各链路长度, 主要是通过计算任意两节点间的最小链路长度,求得从源节点到目的节点间最短通路.23第8讲 分组交换与路由选择固定路由选择固定路由选择Dijkstra算法 对于一个无向图G=(V，E),其中V表示网络中所有节点的集合,E表示网络中所有链路的集合,D(v)为源节点到节点v的距离,l(i, j)为节点i至节点j之间的距离.(1)初始化 任选一个节点作为源节点,不妨不妨令 V=1,对所有不在V中的节点v,写出:145623222
13、1113355图图 求最短路径算法的网络拓扑求最短路径算法的网络拓扑实际编程时一般取D(v)=1000代替.源节点源节点24第8讲 分组交换与路由选择固定路由选择固定路由选择(2)寻找一个不在V中的节点w,其D(w)值为最小.把w加入到V中.然后对所有不在V中的节点,用D(v),D(w)+l(w, v)中较小的值去更新原有的D(v)值,即: D(v) MinD(v),D(w)+l(w, v)(3)重复步骤(2),直到所有的网络节点都在V中为止. 由Dijkstra算法可知,若将已知的各链路长度改为链路时延链路时延,跳数跳数,带宽或费用带宽或费用,就相当于求任意两节点之间具有最小时延,最少跳数,
14、最大带宽或最小费用的通路.所以, 求最短路径算法具有普遍的应用价值.25第8讲 分组交换与路由选择固定路由选择固定路由选择基于左图的网络拓扑结构基于左图的网络拓扑结构,采采用用Dijkstra算法算法,计算以节点计算以节点1为源节点的最短通路的过程为源节点的最短通路的过程.表中带圆圈的数字表示表中带圆圈的数字表示的是的是: 在每一次执行步在每一次执行步骤骤(2)时时, 所寻找到的所寻找到的具有最小值的具有最小值的D(w)值值.步骤步骤 V D(2) D(3) D(4) D(5) D(6)初始化初始化 1 2 5 1 1 1,4 2 4 2 2 1,4,5 2 3 1 4 3 1,2,4,5 3
15、 1 2 4 4 1,2,3,4,5 2 1 2 4 5 1,2,3,4,5,6 2 3 1 2 145623222111335526第8讲 分组交换与路由选择固定路由选择固定路由选择 上述路由表仅是以节点1为源节点,由Dijkstra算法计算得到节点1为根的通路树,然后生成节点1内存中的路由表这样的路由表每个节点都有一个这样的路由表每个节点都有一个,只需分别以这些节只需分别以这些节点为源点点为源点,重新执行算法即可重新执行算法即可.14562322111(0)(1)(2)(3)(4)(5)图图 基于基于Dijkstra算法生成的最短通路树算法生成的最短通路树图图 依据最短通路树生成节点依据最
16、短通路树生成节点1的路由的路由表表目的节点目的节点 下一站下一站123456-24444目的节点目的节点 下一站下一站12*-2427第8讲 分组交换与路由选择随机路由选择随机路由选择当分组到达某个节点时就随机地选择一条链路作为转发的路由.当网络中的节点或链路发生故障时,采用随机走动法是最有效的,它使得路由算法具有较好的稳健性.AKLPEMNDCB信源信源信宿信宿0.50.50.20.20.30.30.30.3图图 随机走动算法示意图随机走动算法示意图0.20.20.20.30.30.30.30.30.30.30.328第8讲 分组交换与路由选择基于流量的路由选择基于流量的路由选择基本思想既考
17、虑拓扑结构，又兼顾网络负荷；前提：每对结点间平均数据流是相对稳定和可预测的；根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。提前离线（off-line）计算29第8讲 分组交换与路由选择基于流量的路由选择基于流量的路由选择需要预知的信息网络拓扑结构；通信量矩阵Fij；线路带宽矩阵Cij；路由算法（可能是临时的）030第8讲 分组交换与路由选择31第8讲 分组交换与路由选择32第8讲 分组交换与路由选择课堂小结课堂小结掌握下面的术语虚电路、数据报、面向连接的服务、无连接服务虚电路、数据报、面向连接的服务、无连接服务路由表路由表、洪泛、洪泛理解网络层的功能和作用掌握分组交换的工作原理理解静态路由策略33第8讲 分组交换与路由选择HomeworkHomework预习第五章中的拥塞控制作业：第217页第2题第5题第8题34
