第 5 章分组交换

,1,第5章分组交换,关于“分组交换”,首先介绍采用分组交换技术的计算机网络及其体系结构；然后讨论分组交换的基本原理及关键技术。,2,分组交换(PacketSwitching)也称为包交换，它是现代计算机网络的技术基础。为了掌握分组交换的功能、原理及其关键技术，必须首先对计算机网络有一个概括的了解。,5.1分组交换计算机网络概述,5.1.1计算机网络的组成5.1.2计算机网络的体系结构原理5.1.3开放系统互连参考模型5.1.4TCP/IP体系结构,3,本节的主要内容,5.1.1计算机网络的组成,计算机为什么要连成网络？计算机连网的主要目的是：（1）实现资源共享，提高资源的利用率，这些资源包括计算资源、存储资源和通信资源等；（2）实现负荷分担，加强计算机之间的互助合作；（3）构成分布式处理系统，提高处理能力和可靠性。,计算机网络的定义：通过通信网络互连、按统一协议（规则）工作的多台计算机的集合。,4,传统的计算机网络由两大部分组成，它们是：通信子网（骨干网）和用户（资源）子网。,计算机网络的基本组成,5,5.1.2计算机网络的体系结构原理,网络协议或规约计算机网络的各计算机之间要交流信息，就必须遵守一些事先约定好的规则。这些规则明确规定了所交换的数据的格式以及有关事件发生的时序。对不同系统的实体之间的信息交流进行控制的一组规则或约定，称为网络协议或规约。,网络协议主要由以下三个要素组成：(1)语法，即数据和控制信息的格式和编码；(2)语义，即各种控制信息的含义及相应的控制操作；(3)同步，即速率适配、事件出现顺序的控制等。,6,假如两台计算机之间要通过一个通信网络传送文件，如何实现？对于非常复杂的网络协议，经验表明最好采用分层（模块）结构，如下图所示。,7,网络层次划分,我们将网络的各层及其协议的集合，称为网络的体系结构（Architecture）。计算机网络的体系结构就是这个计算机网络及其部件应完成的功能的精确定义。需要强调的是，这些功能究竟是用何种硬件或软件完成，则是一个遵循这种体系结构的实现（implementation）的问题。体系结构是抽象的，而实现则是具体的，是真正在运行的计算机硬件和软件。,8,计算机网络体系结构,一、分层,分层就是将一个复杂的系统功能划分为若干相对独立的子功能；每层完成一个子功能；下层为上层服务，上层是下层的用户。,9,根据计算机网络，特别是互联网(Internet)的建设、发展和运行的经验，将复杂的计算机网络的功能分为如右图所示的五层是比较适当的。这五层分别是：应用层、运输层、网络层、数据链路层和物理层。,10,数据在各层之间的传递过程,假定两个主机是直接相连的，计算机1的应用进程AP1向计算机2的应用进程AP2传送数据。,协议数据单元PDU（ProtocolDataUnit）,一个应用进程发送的数据要经过复杂处理过程才能送到对方的应用进程，但对用户来说，这些复杂过程都被以下各层屏蔽掉了，以致应用进程AP1觉得好像是直接把数据交给了应用进程AP2。同理，任何两个同样的层次（图中的水平虚线所示）之间，也好像将数据通过水平虚线直接传递给对方。这就是所谓的“对等层”（PeerLayers）之间的通信。所谓各层协议，实际上就是在各个对等层之间传递数据的各项规则。在文献中常见术语“协议栈”(ProtocolStack)，这是因为几个层次画在一起很像一个堆栈。,11,“对等层”与“协议栈”的概念,二、实体、协议、服务、以及服务接入点,实体(Entity)表示信息的任何发送者或接收者(可发送或接收信息的硬件或软件进程)。在许多情况下，实体就是一个特定的软件模块。协议是控制两个对等实体进行通信的规则的集合。协议的语法方面的规则定义了所交换的信息的格式，而协议的语义方面的规则定义了发送者或接收者所要完成的操作。在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务。而要实现本层协议，还需要使用下一层所提供的服务。,12,首先，协议的实现保证了能够向上一层提供服务。本层的服务用户只能看见服务而无法看见下面的协议。下面的协议对上面的服务用户是透明的。其次，协议是“水平的”，即协议是控制对等实体之间通信的规则。但服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。还应注意，并非在一个层内完成的全部功能都称为服务。只有那些能够被高一层看得见的功能才能称之为“服务”。上层使用下层所提供的服务必须通过层间交换的命令来实现，这些命令称为服务原语。,13,“协议”与“服务”在概念上的区别,交换分为电路交换(CS)和分组交换(PS)。这两种交换的机制存在本质的区别。理论与实际均已表明，按照电话业务的特征设计的电路交换不适合于计算机数据通信，而分组交换则是根据数据业务的特征设计的交换技术。,5.2分组交换原理,5.2.1电路交换技术不适合计算机数据通信5.2.2异步时分复用5.2.3分组存储转发5.2.4分组交换方式（数据报和虚电路）,14,本节的主要内容,15,5.2.1电路交换技术不适合计算机数据通信,电路交换是根据用户的呼叫请求，由网络预先给用户分配传输带宽。在通话的全部时间内用户始终占用端到端的固定传输带宽。利用电路交换可以实现计算机之间的数据通信，但计算机数据通常是随机而突发地出现的，因此电路交换所建立的物理通路用来传送数据的效率很低。另外，由于计算机和各种终端的传送速率不一样，而电路交换所分配的带宽是固定的或量化的，因此缺乏灵活性。由此可见，必须寻找出新的适合于计算机通信的交换技术，这就要求改变传统的交换方式。,16,5.2.2异步时分复用,17,5.2.3分组存储转发,分组交换是一种存储转发式的交换方式，其存储转发的基本数据单元是报文的分组（Packet）。在电信网中，电报通信用的是存储转发式，存储转发的基本单位是电报的报文，称为报文交换。分组交换是报文交换的继承和发展。分组交换继承了存储转发这一交换机制，但存储转发的基本数据单元是分组（又称为包）。报文一般较长，分组通常是报文的一段。分组与报文的关系如下图所示。,18,采用分组交换技术的通信网或通信子网称为分组交换网(如下图)。分组交换网由交换结点和链路组成，链路的传输采用分组复用，而结点的交换采用分组交换。,分组交换网,19,结点交换机处理分组的过程是：将收到的分组先放入缓冲区，再查找路由表，然后确定将该分组交给某个端口转发出去。一个分组交换网可以容许很多主机同时进行通信，而一个主机中的多个进程也可以各自和不同主机中的不同进程进行通信。采用存储转发的分组交换，实质上是采用了在数据通信的过程中断续(或动态)分配传输带宽的策略，这对传送突发式的计算机数据非常合适，使得通信线路的利用率大大提高。分组交换网常采用网状拓扑结构，当发生网络拥塞或少数结点、链路出现故障时，可灵活地改变路由而不致引起通信的中断或全网的瘫痪。,交换机处理分组的过程,20,分组交换的优点和存在的问题,分组交换也带来一些新的问题，分组在各结点存储转发时，因为要排队等待，总会造成一定的时延。当网络通信量大时，这种时延也可能会很大。此外，各分组必须携带的控制信息也造成了一定的额外开销。整个分组交换网还需要专门的管理和控制机制。,21,5.2.4分组交换方式,数据报分组交换在传送数据之前，不需要预先建立任何连接，而是直接按照每个分组首部中的目的地址独立选择转发路径。优点数据报方式路由灵活，便于绕过过于繁忙或发生故障的结点或链路，并且比较适合于短报文的传送。缺点数据报方式可能引起属于同一报文的各个分组的乱序。因此，属于同一报文的分组需要编排序号。此外，数据报提供的是一种“尽力传送”的服务。,一、数据报,22,数据报方式示意图,23,虚电路方式是在用户数据传送前，先要通过发送呼叫请求分组建立端到端之间的连接通路。这种连接通路称为虚通路或虚电路(VC)。在虚电路方式下，属于同一呼叫的各个数据分组均沿着同一虚电路流动(路由相同)。由于虚电路所经过的各条物理链路是采用异步时分复用方式传输分组的，故虚电路连接不同于电路交换中的物理连接，而是逻辑连接。在一条物理线路上可以同时存在多个虚电路，也就是支持多个逻辑连接。虚电路实际使用的带宽取决于单位时间内传输的分组数，因而带宽的分配是动态的。,二、虚电路,24,虚电路方式示意图,25,虚电路的好处是所有发送的分组都按发送的前后顺序进入管道，然后按照先进先出的原则沿着虚电路传送到目的主机，分组不会因网络出现拥塞而丢失(建立虚电路连接时，在结点交换机中预留了缓冲区)，而且分组到达目的主机的顺序与发送时的顺序一致。此外，还可以采取连接接纳控制等措施进行流量控制。因此虚电路对通信的服务质量QoS有比较好的保证。虚电路有两种建立方式：交换虚电路(SVC)和永久虚电路(PVC)。通过用户发送呼叫请求分组建立的虚电路称为SVC。根据用户预约，由网络运营者为之建立的永久性虚电路，称之为PVC。,采用虚电路方式的好处,26,三、虚电路与数据报的比较,27,5.3分组交换网的路由选择,5.3.1路由问题概述5.3.2非自适应路由选择5.3.3自适应路由选择,分组交换网的主要功能是将分组从源结点传送到目的结点。由于源结点和目的结点不一定相邻，中间可能要经过若干结点和结点间的链路，因此必须为分组选择路由，即确定传送路径。那么路由应该如何表示？网络依据什么信息来进行路由选择？路由选择应该采取哪些策略和算法？这些就是本节要讨论的问题。,本节的主要内容,28,(1)标头指示法标头指示法是由源结点将路由信息标识在每个分组的标头中，故又称为源路由法。中转结点交换机根据分组的标头，可知道将该分组转发到那个端口(链路)。因此每个分组的传送路径在它进入网络之前就必须确定。如图所示，假定分组的路径为ACED，可将这四个结点的编号和相应的链路标识在分组标头域中。被标识的结点和链路的出现顺序，应与分组穿越网络的次序相符。,5.3.1路由问题概述,一、路由表示法,29,(2)路由表法每个结点交换机中保持着一个路由表，这个路由表是根据采用的路由选择算法预先或实时地计算出来的，它以表格的形式列出了分组从该结点传送到任意目的结点的路由信息。右图网络各结点的路由表如下图。,路由表,30,路由表的简化,为了消除路由表中的重复项目，可以用一个默认路由(符号“*”)代替所有具有相同“下一站”的项目。默认路由比其它项目的优先级低。下图为使用了默认路由的简化路由表，只有超过一个以上的目的结点有相同的下一结点时才使用默认路由。目前广域分组交换网大都采用路由表法实现分组的转发，同时也可以支持标头指示法，下面集中讨论得到最广泛应用的路由表法。,31,路由表的简化,路由问题就是解决分组交换网中的各结点交换机应该如何进行分组转发的问题，因此有必要先研究网络的拓扑结构。(1)用图表示网络可以用图论中的“图”(Graph)表示一个分组交换网络，图的“顶点”表示网络结点，连接顶点的“边”表示网络链路。例如，网络图G=(V,E)，其中，V是网络结点的集合，E是链路的集合。可用一组链路的有序集(l1,l2,ln)来表示网络的一条有向通路(Path)，该通路称为“分组传送路径”(Route)。因此，所谓“路由算法”或“路径选择算法”，就是指确定分组从它的源点到达目的点的有向传输通路的法则。,二、路由选择算法,32,路由表的简化,考虑下图所示的网络，网络图G=(V,E)，其中，V=(A,B,C,D,E,F)，E=(l1,l2,l10)。假设有一分组欲从A点传送到D点，它可以选择几条不同的通路，分别表示为ABD、ACED和ACD，等等。用链路的有序集表示，则为(l1,l3)、(l2,l4,l7)和(l2,l6)，等等。,通路（路径）的表示,A,C,E,F,D,B,l6,l1,l10,l4,l7,l8,l5,l2,l3,l9,33,一个理想的路由选择算法应满足如下要求：1）算法必须是正确的和完整的。2）算法在计算上应尽可能简单。3）算法要有自适应性。4）算法应具有稳定性。5）算法应是公平的。6）算法应是最佳的。,（2）理想的路由选择算法,现在，我们面临的问题是：采用什么算法来选择合适的路径？依据什么信息来进行这种选择？应该如何执行这种选择的策略？用什么标准来评判所选择路径的好坏？下面就讨论路由选择的一般原理以及几种不同的路由选择策略和算法。,34,路由选择算法是解决如何根据网络拓扑和状态，按照一定的性能准则，计算分组传送路径的问题。路由策略是解决路由的选择能否适应网络拓扑和状态变化的问题。路由选择算法仅是路由策略的一部分。从路由的选择能否随网络的变化而自适应地进行调整变化来区分，路由策略可分为两大类，即非自适应路由选择策略与自适应路由选择策略。非自适应路由选择也叫做静态路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。自适应路由选择也叫做动态路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂。,三、路由策略的分类,35,5.3.2非自适应路由选择,该方法是在每个结点上保持一张路由表，表上标明去每一个目的结点的分组应从哪条链路进行转发。路由表是在整个系统进行配置时生成的，并且在此后的一段相当时间内保持固定不变。当网络拓扑固定不变并且通信流量相对稳定时，采用该方法是适当的。这种路由选择策略的关键是要算出给定网络中任意两个结点之间的最短路径，然后制作出相应的路由表。,非自适应路由选择主要有：固定路由法、概率路由法和洪泛法。,一、固定路由法,36,Dijkstra算法,37,整个算法包括以下两个部