搜索
第8讲分组交换与路由选择第8讲分组交换与路由选择课时授课计划课程内容第8讲分组交换与路由选择内容：电路交换和分组交换虚电路和数据报路由选择策略目的与要求：掌握电路交换和分组交换的基本工作原理；掌握网络提供的服务方式：虚电路和数据报服务；理解路由选择算法；重点与难点：重点：分组交换的工作原理、路由选择算法；难点：路由选择算法。第8讲分组交换与路由选择课堂讨论：分组交换的工作原理？网络层提供的基本服务之一：路由选择？现代教学方法与手段：投影PowerPoint幻灯课件复习（提问）：IEEE体系结构？CSMA/CD和Tokenring？第8讲分组交换与路由选择第5章网络层5.1电路交换和分组交换5.2虚电路和数据报5.3路由选择第8讲分组交换与路由选择网络层讨论：为什么需要网络层？网络层提供哪些服务?为什么网络互连中需要路由器等路由设备？第8讲分组交换与路由选择OSI/RMApplicationprotocolRepresentationprotocolSessionprotocolTransportprotocolAPDUPPDUFrameBitsPacketSPDUSegment第8讲分组交换与路由选择为什么需要网络层主机A主机B结点1结点2结点3网络连接数据链路连接数据链路连接传输层数据链路层网络层网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节，如子网类型、拓扑结构、子网数目，向上层提供一致的服务、统一的地址第8讲分组交换与路由选择交换通信网的数据交换方式电路交换（circuitswitching）分组交换（packetswitching）第8讲分组交换与路由选择电路交换电路交换的数据传输过程电路的建立数据传输电路释放电路交换的特点：时延小，适合于实时性强的交互式通信；对突发性通信不适应，信道利用率低；不具备存储数据或差错控制能力第8讲分组交换与路由选择电路交换12345DTEDCEDCEDTEDCEDCEDCEDCEDTEDTEDTE6ABCDE返回第8讲分组交换与路由选择分组交换分组交换的数据传输过程仍基于存储转发原理，但对数据传输单位的作了划分：将长报文或大的数据块分割成小段，为每小段附上地址、分组编号、校验等信息构成一个数据分组（数据包），作为存储转发的逻辑数据单元。电路交换的特点：固定大小的分组单位较小，可充分利用线路空闲，从而减少了传输延时；出错重传的数据量也大大减少第8讲分组交换与路由选择分组交换虚电路（VirtualCircuit）数据报（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入口出口AAH23010E001DD入口出口BBE010H4001EH4入口出口H3B4000E002D入口出口BDC000H5010DABCDEA2C0H5CH4虚电路路由表建立过程示例第8讲分组交换与路由选择虚电路特点：包传输路径相同，不需要源地址与目标地址信息。除了建立连接时需要路由，在数据传送过程中不需要作路由，无路由信息，只有虚电路连接信息。包的传输不会出现丢失、重复和乱序现象。分类：永久虚电路（PVC）呼叫虚电路（SVC）第8讲分组交换与路由选择数据报通信子网借以实现面向无连接服务的工作方式。为每个分组选择独立的路由，即不同的分组可以走不同的路由。第8讲分组交换与路由选择数据报AEDCBH2H3H1H4H512目的站输出线BCDE1212结点A的路由表数据报的路由表每个分组都需要携带完整的目的地址。每个结点保存一个到网内其他结点的输出线选择表第8讲分组交换与路由选择虚电路与数据报的比较数据报子网虚电路子网延时分组传播延时电路建立，分组传输延时路由选择每个分组单独选择路由建立虚电路时选择路由，以后所有分组都是用该路由状态信息子网无需保存状态信息每个节点要保存一张路由表地址每个分组包括源端和目的端的完整地址每个分组含有一个短的虚电路号节点失败的影响除了在崩溃时正在由该节点处理的分组都丢失外，无其它影响所有经过失败节点的虚电路都要被终止拥塞控制难如果有足够的缓冲区分配给已经建立的虚电路，则容易控制第8讲分组交换与路由选择路由选择理想路由算法的基本特性正确性（Correctness）简单性（Simplicity）健壮性（robustness）稳定性（stability）公平性（fairness）优越性（optimality）高效性（efficiency）第8讲分组交换与路由选择路由选择静态路由策略扩散法固定路由选择随机路由选择基于流量的路由选择动态路由策略在网络互联中讲解第8讲分组交换与路由选择扩散法(洪泛)基本思想把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。主要问题洪泛要产生大量重复包。解决措施每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包；记录包经过的路径AKLPEMNDCB图洪泛算法示意图信源第8讲分组交换与路由选择扩散法(洪泛)选择性洪泛算法（selectiveflooding）洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况路由器和线路的资源过于浪费，实际很少直接采用；具有极好的健壮性，可用于军事应用；作为衡量标准评价其它路由算法。第8讲分组交换与路由选择固定路由选择固定路由选择在每个节点上保持一张路由表,表上标明对每一个目的地址应走哪条链路进行转发.路由表是在整个系统进行配置时生成的.配置时根据事先计算好的“网络中任意两个节点之间最短路径”,将这些最短通路制成路由表,存放在各个节点中.每一个分组都可在所到达的节点中查找下一步应转发到哪一个节点(下一站节点或后继节点).经典的求最短路径算法是Dijkstra算法.它的条件是已知网络的拓扑和各链路长度,主要是通过计算任意两节点间的最小链路长度,求得从源节点到目的节点间最短通路.第8讲分组交换与路由选择固定路由选择Dijkstra算法对于一个无向图G=(V，E),其中V表示网络中所有节点的集合,E表示网络中所有链路的集合,D(v)为源节点到节点v的距离,l(i,j)为节点i至节点j之间的距离.(1)初始化任选一个节点作为源节点,不妨令V={1},对所有不在V中的节点v,写出:1456232221113355不直接相连与节点若节点直接相连与节点若节点11),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)←Min[D(v),D(w)+l(w,v)](3)重复步骤(2),直到所有的网络节点都在V中为止.由Dijkstra算法可知,若将已知的各链路长度改为链路时延,跳数,带宽或费用,就相当于求任意两节点之间具有最小时延,最少跳数,最大带宽或最小费用的通路.所以,求最短路径算法具有普遍的应用价值.第8讲分组交换与路由选择固定路由选择基于左图的网络拓扑结构,采用Dijkstra算法,计算以节点1为源节点的最短通路的过程.表中带圆圈的数字表示的是:在每一次执行步骤(2)时,所寻找到的具有最小值的D(w)值.步骤VD(2)D(3)D(4)D(5)D(6)初始化{1}251∞∞1{1,4}24①2∞2{1,4,5}231②43{1,2,4,5}②31244{1,2,3,4,5}2③1245{1,2,3,4,5,6}2312④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讲分组交换与路由选择Homework预习第五章中的拥塞控制作业：第217页第2题第5题第8题