数据通信与计算机网络--08分组交换

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