《分组交换》PPT课件.ppt

,第 5 章 分组交换,教学大纲要求：1.基本要求（1）掌握计算机网络的组成和OSI协议体系结构。（2）掌握分组交换原理。（3）掌握分组交换网的路由选择。2.重点、难点 重点：分组交换原理，路由选择方法，特别是自适 应路由选择策略。难点：存储转发，寻址与路由问题。3.说明 以分组交换原理为主线，适当介绍相关内容。,1,关于“分组交换”,现代交换技术基本上分为电路交换和分组交换，这一章我们先先介绍采用分组交换技术的计算机网络及其体系结构；然后讨论分组交换的基本原理及关键技术。本章主要涉及传统的分组交换，而新型分组交换将在后续的章节中讨论。,2,分组交换(Packet Switching)也称为包交换，它是现代计算机网络的技术基础。为了掌握分组交换的功能、原理及其关键技术，必须首先对计算机网络有一个概括的了解。,5.1 分组交换计算机网络概述,5.1.1 计算机网络的组成5.1.2 计算机网络的体系结构原理 开放系统互连参考模型5.1.4 TCP/IP体系结构,3,本节的主要内容,5.1.1 计算机网络的组成,计算机为什么要连成网络？计算机连网的主要目的是：（1）实现资源共享，提高资源的利用率，这些资源包括计算资源、存储资源和通信资源等；（2）实现负荷分担，加强计算机之间的互助合作；（3）构成分布式处理系统，提高处理能力和可靠性。,计算机网络的定义：通过通信网络互连、按统一协议（规则）工作的多台计算机的集合。,4,传统的计算机网络由两大部分组成，它们是：通信子网（骨干网）和用户（资源）子网。,计算机网络的基本组成,5,实际传送信息的通信子网有多个,5.1.2 计算机网络的体系结构原理,网络协议或规约 计算机网络的各计算机之间要交流信息，就必须遵守一些事先约定好的规则。这些规则明确规定了所交换的数据的格式以及有关事件发生的时序。对不同系统的实体之间的信息交流进行控制的一组规则或约定，称为网络协议或规约。,网络协议主要由以下三个要素组成：(1)语法，即数据和控制信息的格式和编码；(2)语义，即各种控制信息的含义及相应的控制操作；(3)同步，即速率适配、事件出现顺序的控制等。,6,假如两台计算机之间要通过一个通信网络传送文件，如何实现？对于非常复杂的网络协议，经验表明最好采用分层（模块）结构，如下图所示。,7,网络层次划分,可以将通过网络传送文件的工作分为三类：第一类工作与传送文件直接相关，例如确信对方做好接受准备，文件格式转换等。两个模块之间的虚线表示两个计算机系统文件交换的一些命令等第二类工作设立一个通信模块，用来保证文件和文件传送命令能可靠地在两端系统之间交换。而且它还可以为别的比如邮件提供可靠通信服务。第三类工作是网络接入，负责做网络接口细节为上层提供服务。,我们将网络的各层及其协议的集合，称为网络的体系结构（Architecture）。计算机网络的体系结构就是这个计算机网络及其部件应完成的功能的精确定义。需要强调的是，这些功能究竟是用何种硬件或软件完成，则是一个遵循这种体系结构的实现（implementation）的问题。体系结构是抽象的，而实现则是具体的，是真正在运行的计算机硬件和软件。,9,计算机网络体系结构,一、分层,分层就是将一个复杂的系统功能划分为若干相对独立的子功能；每层完成一个子功能；下层为上层服务，上层是下层的用户。,10,根据计算机网络，特别是互联网(Internet)的建设、发展和运行的经验，将复杂的计算机网络的功能分为如右图所示的五层是比较适当的。这五层分别是：应用层、运输层、网络层、数据链路层和物理层。,物理层的任务就是利用物理信道“透明”地传输比特流。在物理层上所传数据的基本单位是比特。传输信息利用的物理信道是以双绞线、同轴电缆、光纤、微波无线电等传输媒质为基础的信号通路。“透明地传输比特流”表示经实际信道可以传输任意的比特组合。实际信道对传输的信号是有损伤的，其中最主要的损伤是信号波形发生畸变和加入了噪声，从而使传输比特发生差错。物理层就是要尽可能地减小这些损伤，达到“透明”传输。物理层要规定与信道（传输媒质）的接口，包括接口的电气特性、机械特性、功能特性和工作时序。,11,(1)物理层(Physical Layer),数据链路层的基本任务是在两个相邻结点之间的链路上实现以帧(Frame)为单位的“无误”数据传输。帧有两种类型：数据帧和控制帧。数据帧包含数据和必要的控制信息；控制帧主要包含控制信息，但也可搭载少量数据信息。在每一帧所包括的控制信息中，有用于帧同步、寻址、差错控制以及流量控制等的信息。数据链路层的具体功能包括链路连接控制、差错控制(ARQ)和流量控制(收发速率适配)等。链路层可为上一层提供两种服务方式，面向连接方式和无连接方式。链路连接控制只在有连接方式下采用。,12,(2)数据链路层(Data Link Layer),网络层的基本任务是将数据从源(结)点传送到目的(结)点。在源点与目的点(或称终点)之间可能要经过许多个结点和链路，还可能要经过好几个不同的子网。网络层数据传送的基本单位是分组(Packet)，又称为包。因此，网络层的主要功能就是实现分组交换，即根据分组首部所提供的寻址信息，选择合适的路由，使数据分组经过沿途结点的转发准确无误地到达终点。网络层为它的上一层提供面向连接的服务或无连接的服务。,13,(3)网络层(Network Layer),运输层的基本任务是实现主机进程与主机进程之间的信息传送。在运输层，信息的传送单位是报文(Message)。当报文较长时，先要把它分割成若干段，然后再交给下一层（网络层）进行传送。运输层根据通信子网的特性最佳地利用网络资源，并以可靠和经济的方式，透明地传送报文。运输层根据应用层的需要向上一层提供面向连接的可靠数据传送服务或无连接非可靠的数据传送服务。为了实现可靠传送，运输层要完成端到端的连接控制、差错控制、流量控制和拥塞控制等功能。,14,(4)运输层(Transport Layer),应用层确定进程之间通信的性质以满足用户的需要。应用层不仅要提供应用进程所需要的信息交换和远程操作，而且还要作为互相作用的应用进程的用户代理(User Agent)，来完成一些为进行语义上有意义的信息交换所必须的功能。典型的应用层协议有支持文件传送的FTP协议、支持电子邮件的SMTP协议、支持万维网(WWW)的HTTP协议。,15,(5)应用层(Application Layer),在网络体系结构中，应用层和运输层合称为高层；网络层、数据链路层和物理层合称为低层。主机或端系统要完成所有各层的功能；而通信子网的各个结点和子网之间的路由器中只需完成低层功能。,16,数据在各层之间的传递过程,假定两个主机是直接相连的，计算机1的应用进程AP1向计算机2的应用进程AP2传送数据。,协议数据单元 PDU（Protocol Data Unit）,当计算机2接收到一串比特流的时候，就从第1层开始往上传，每一层都会根据头部控制信息作些必要的操作，再往上传一层就剥离该层的PDU控制信息。最后把应用信息进程AP1的数据交给目的主机的应用进程AP2。,假定计算机1的应用进程AP1向计算机2的应用进程AP2传送数据。AP1先将数据交给第5层，第5层加上必要的控制信息H5变成这一层的协议数据单元PDU,交给下一层，第4层收到这个单元后也加上本层的控制信息H4形成本层的PDU，再交给第3层，依次类推，到了第2层(数据链路层)控制信息分成两部分，加在首部H2和尾部T2。最后通过物理信道以比特流的形式传输到对方。,一个应用进程发送的数据要经过复杂处理过程才能送到对方的应用进程，但对用户来说，这些复杂过程都被以下各层屏蔽掉了，以致应用进程 AP1觉得好像是直接把数据交给了应用进程 AP2。同理，任何两个同样的层次（图中的水平虚线所示）之间，也好像将数据通过水平虚线直接传递给对方。这就是所谓的“对等层”（Peer Layers）之间的通信。所谓各层协议，实际上就是在各个对等层之间传递数据的各项规则。在文献中常见术语“协议栈”(Protocol Stack)，这是因为几个层次画在一起很像一个堆栈。,19,“对等层”与“协议栈”的概念,二、实体、协议、服务、以及服务接入点,实体(Entity)表示信息的任何发送者或接收者(可发送或接收信息的硬件或软件进程)。在许多情况下，实体就是一个特定的软件模块。协议是控制两个对等实体进行通信的规则的集合。协议的语法方面的规则定义了所交换的信息的格式，而协议的语义方面的规则定义了发送者或接收者所要完成的操作,比如何种情况下数据必须重传或丢弃。在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务。而要实现本层协议，还需要使用下一层所提供的服务。,20,首先，协议的实现保证了能够向上一层提供服务。本层的服务用户只能看见服务而无法看见下面的协议。下面的协议对上面的服务用户是透明的。其次，协议是“水平的”，即协议是控制对等实体之间通信的规则。但服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。还应注意，并非在一个层内完成的全部功能都称为服务。只有那些能够被高一层看得见的功能才能称之为“服务”。上层使用下层所提供的服务必须通过层间交换的命令来实现，这些命令称为服务原语。,21,“协议”与“服务”在概念上的区别,22,SAP 和 SDU,开放系统互连参考模型,国际标准化组织（ISO,International Standard Organization）制定的开放系统互连（OSI,Open System Interconnection）参考模型采用7个层次的网络体系结构，也就是将前面所讲的原理性体系结构中的应用层再划分为3个层次，其余4层保持不变。这3个层次从上到下的名称是：应用层、表示层和会话层。,23,（1）会话层（Session Layer）,会话层为应用实体间的会话提供控制机理，包括会话连接控制及通信双方的同步。,会话层提供的一种服务是：会话管理，允许会话双方进行全双工或分时半双工。在分时半双工通信的情况下，会话层负责双方的同步，保证双方不同时发送数据，实时控制双方收发转换。这可以通过双方交换令牌(Token)来实现，令牌是发送权的标记，只有持有令牌的一方才有权发送数据。,表示层和应用层,表示层负责应用层实体传送数据的格式转换，实现数据编码/解码、数据压缩/解压、数据加密/解密等功能。为了使用采用不同数据表示法的计算机之间能进行通信，使用的数据结构可以抽象的方式来定义，并使用标准的编码方式，表示层管理这些抽象数据结构，并在计算机内部完成原始表示法和网络表示法之间的转换。,25,（2）表示层（Presentation Layer）,应用层负责为用户提供接入OSI环境的方法，支持各种应用，如网络虚拟终端、文件传送、电子邮件、多媒体、WWW等。OSI的7层体系结构中，下面的四层，即物理层，数据链路层，网络层，传输层与前面介绍的完全相同。其实分层，实体，对等层协议，协议数据单元，服务，原语等概念都是来自OSI参考模型。,（3）应用层（Application Layer）,5.1.4 TCP/IP体系结构,互联网(Internet)使用的TCP/IP体系在计算机网络领域占有重要地位。在Internet的各种协议中，最重要的是传输控制协议TCP和网际协议IP，而TCP/IP往往是表示Internet所使用的体系结构或整个TCP/IP协议族。,27,TCP/IP体系共有4个层次，从上到下分别是应用层、运输层、网际层和网络接口层。TCP/IP与OSI体系结构的对比如右图所示。,应用层 这层中有许多著名协议，如远程登录协议TELNET、文件传送协议FTP、简单邮件传送协议SMTP等。运输层 这层可使用两种不同的协议，一种是面向连接的传输控制协议TCP。另一种是无连接的用户数据报协议UDP。运输层的协议数据单元是报文（段）或数据流。网际层 主要协议是无连接的网际协议IP。网际层的协议数据单元是IP数据报或IP分组。与网际协议IP配合使用的还有三个协议，这就是Internet控制报文协议ICMP、地址解析协议 ARP和逆地址解析协议RARP。网络接口层 由于TCP/IP在设计时考虑到要与具体的物理网络无关，因此在TCP/IP的标准中并没有对数据链路层和物理层做出规定，TCP/IP体系中只是指出主机必须使用某种协议接入网络，以便能在其上传递IP分组。,28,TCP/IP 体系各层协议概述,TCP/IP 与 OSI 的比较,(1)TCP/IP一开始就考虑到多种异构网的互连问题，并将网际协议IP作为TCP/IP的重要组成部分。但ISO和CCITT最初只考虑到使用一种标准的公用数据网将各种不同的系统互连在一起。ISO认识到了网际协议IP的重要性后，只好在网络层中划分出一个子层来完成类似TCP/IP中IP的作用。(2)TCP/IP一开始就确定面向连接服务和无连接服务并重，而OSI在开始时只强调面向连接服务。一直到很晚OSI才开始制定无连接服务的有关标准。(3)TCP/IP较早就有较好的网络管理功能，而OSI到后来才开始考虑这个问题。,29,TCP/IP 的不足之处,TCP/IP的模型对“服务”、“协议”和“接口”等概念并没有很清楚地区分开。因此在使用一些新技术来设计新的网络时，采用这种模型就可能会遇到一些麻烦。TCP/IP模型的通用性较差，很难用它来描述其他种类的协议栈。TCP/IP的网络接口层严格来说并不是一个层次而仅仅是一个接口，而在网络层下面的数据链路层和物理层则根本没有。但实际上这两个层次还是很重要的。,30,通信子网的任务是将数据信息从源点传送到目的点，之间要经过很多链路和中继节点，链路的功能是传输，中继节点功能是交换，交换分为电路交换(CS)和分组交换(PS)。这两种交换的机制存在本质的区别。理论与实际均已表明，按照电话业务的特征设计的电路交换不适合于计算机数据通信，而分组交换则是根据数据业务的特征设计的交换技术。,5.2 分组交换原理,5.2.1 电路交换技术不适合计算机数据通信 5.2.2 异步时分复用 5.2.3 分组存储转发 5.2.4 分组交换方式（数据报和虚电路）,31,本节的主要内容,32,5.2.1 电路交换技术不适合 计算机数据通信,电路交换是根据用户的呼叫请求，由网络预先给用户分配传输带宽。用户呼叫成功，主叫端到被叫端则建立了一条物理通路，在通话的全部时间内用户始终占用端到端的固定传输带宽。利用电路交换可以实现计算机之间的数据通信，计算机代替电话终端，需要设置一个网络接口设备，即调制解调器，优点是通路建立后，端到端的传输延时极少，适合承载对时延要严格要求的数据业务，但计算机数据通常是随机而突发地出现的通信线路利用不到10%，因此电路交换所建立的物理通路用来传送数据的效率很低。,另外，由于计算机和各种终端的传送速率不一样，采用电路交换不同类型，不同规格，不同速率的终端很难相互通信，而电路交换所分配的带宽是固定的或量化的，因此缺乏灵活性，而且电路交换通话双方建立的通路中的任何一个点出了故障就必须重新拨号建立链接。由此可见，必须寻找出新的适合于计算机通信的交换技术，这就要求改变传统的交换方式。,34,5.2.2 异步时分复用,同步时分复用通过时隙在TDM帧内的位置来区分不同的信息通路，在一个端到端的电路链接建立以后沿途链路的时隙占用关系就完全确定了，并且一直保持直到链接释放，因此在一条链路持续时间内不管用户是否发送信息都要占用时隙占用信道资源。图5-9假定有4个数据用户ABCD复用一条链路来传输，在第一个时隙AB有数据发送，CD无数据发送，在第二个时隙BC有数据而AD无数据。如果采用同步时分复用，每一帧都有4个时隙第一到第四个时隙分别分配给ABCD当某个数据源无数据发送相应的时隙就空闲，不能被其他用户使用，但是如果采用异步时分复用用时隙标题区分各路数据。可以充分利用空闲时隙传输数据。,异步时分复用虽然也分时隙，但是不通过时隙位置，而是通过时隙的标头信息来区分不同的信息通路，用户若没有信息发送，则不占用时隙，信道的利用率得以提高。代价是标头的开销，标头一般若干个字节，为了减小开销，时隙长度需增加，是一个包含许多字节的分组，异步时分复用又叫分组复用。异步时分复用是分组交换的技术基础。有了时隙标头之后，时隙(分组)既可以定长也可以变长。,37,5.2.3 分组存储转发,分组交换是一种存储转发式的交换方式，其存储转发的基本数据单元是报文的分组（Packet）。在电信网中，电报通信用的是存储转发式，存储转发的基本单位是电报的数据报文，称为报文交换。分组交换是报文交换的继承和发展。分组交换继承了存储转发这一交换机制，但存储转发的基本数据单元是分组（又称为包）。报文一般较长，分组通常是报文的一段。分组与报文的关系如下图所示。,存储转发的原理 邮件的传递过程就是发端局（中转局）把一定时间里收到的信件存起来，进行分拣，然后进行转发，信件的传递过程就是一个典型的存储转发过程。分组交换里面的每个分组由首部和数据两部分组成，分组的首部包含比如目的地和源地址等重要的控制信息，网络节点，只需处理首部即可获知将分组发往何处。,39,采用分组交换技术的通信网或通信子网称为分组交换网(如下图)。分组交换网由交换结点和链路组成，链路的传输采用分组复用，而结点的交换采用分组交换。,分组交换网,40,结点交换机处理分组的过程是：将收到的分组先放入缓冲区，再查找路由表，然后确定将该分组交给某个端口转发出去。一个分组交换网可以容许很多主机同时进行通信，而一个主机中的多个进程也可以各自和不同主机中的不同进程进行通信。采用存储转发的分组交换，实质上是采用了在数据通信的过程中断续(或动态)分配传输带宽的策略，这对传送突发式的计算机数据非常合适，使得通信线路的利用率大大提高。分组交换网常采用网状拓扑结构，当发生网络拥塞或少数结点、链路出现故障时，可灵活地改变路由而不致引起通信的中断或全网的瘫痪。,交换机处理分组的过程,41,分组交换的优点和存在的问题,分组交换也带来一些新的问题，分组在各结点存储转发时，因为要排队等待，总会造成一定的时延。当网络通信量大时，这种时延也可能会很大。此外，各分组必须携带的控制信息也造成了一定的额外开销。整个分组交换网还需要专门的管理和控制机制。,42,5.2.4 分组交换方式,数据报分组交换在传送数据之前，不需要预先建立任何连接，而是直接按照每个分组首部中的目的地址独立选择转发路径。优点 数据报方式路由灵活，便于绕过过于繁忙或发生故障的结点或链路，并且比较适合于短报文的传送。缺点 数据报方式可能引起属于同一报文的各个分组的乱序。因此，属于同一报文的分组需要编排序号。此外，数据报提供的是一种“尽力传送”的服务。,一、数据报,数据报服务的特点是：主机只要想发送数据随时可以发送，每个分组独立在网络内部流动，路由灵活，便于绕过过于繁忙或发生故障的节点或链路，比较适合于短报文传送，在传送多分组报文时由于各分组独立选路，先发送的分组不一定先到达目的地，因此需要对属于同一报文的分组编排序号。当网络发生拥塞时，网络中的某个节点可能将一些分组丢失，所以数据报提供的服务是不能保证服务质量，是一种“尽力传送”服务。,44,数据报方式示意图,45,虚电路方式是在用户数据传送前，先要通过发送呼叫请求分组建立端到端之间的连接通路。这种连接通路称为虚通路或虚电路(VC)。在虚电路方式下，属于同一呼叫的各个数据分组均沿着同一虚电路流动(路由相同)，分组的路由选择是以呼叫为单位的，而不是以单个分组为单位进行的。由于虚电路所经过的各条物理链路是采用异步时分复用方式传输分组的，故虚电路连接不同于电路交换中的物理连接，而是逻辑连接，并不独占物理线路。在一条物理线路上可以同时存在多个虚电路，也就是支持多个逻辑连接。虚电路实际使用的带宽取决于单位时间内传输的分组数，因而带宽的分配是动态的。,二、虚电路,46,主机要通信首先要发起一个虚呼叫VC即一个特定格式的“呼叫请求”控制分组到目的主机，要求建立连接，同时寻找合适的路由，目的主机同意通信就发回一个“呼叫接受”的响应分组，然后就可以传送数据分组，数据传送完毕后要释放该虚电路。需要注意的是采用了存储转发技术，虚电路的分组交换只是断续的占用一段又一段的链路，并没有真正独占该物理电路，这一点跟电路交换里面在通话期间自始至终占用一条端到端的物理信道是不同的。,47,虚电路方式示意图,48,虚电路的好处是所有发送的分组都按发送的前后顺序进入管道，然后按照先进先出的原则沿着虚电路传送到目的主机，分组不会因网络出现拥塞而丢失(建立虚电路连接时，在结点交换机中预留了缓冲区)，而且分组到达目的主机的顺序与发送时的顺序一致。此外，还可以采取连接接纳控制等措施进行流量控制。因此虚电路对通信的服务质量QoS有比较好的保证。虚电路有两种建立方式：交换虚电路(SVC)和永久虚电路(PVC)。通过用户发送呼叫请求分组建立的虚电路称为SVC。根据用户预约，由网络运营者为之建立的永久性虚电路，称之为PVC，不需建立连接直接传输。,采用虚电路方式的好处,49,三、虚电路与数据报的比较,50,5.3 分组交换网的路由选择,5.3.1 路由问题概述 5.3.2 非自适应路由选择5.3.3 自适应路由选择,分组交换网的主要功能是将分组从源结点传送到目的结点。由于源结点和目的结点不一定相邻，中间可能要经过若干结点和结点间的链路，因此必须为分组选择路由，即确定传送路径。那么路由应该如何表示？网络依据什么信息来进行路由选择？路由选择应该采取哪些策略和算法？这些就是本节要讨论的问题。,本节的主要内容,51,(1)标头指示法 标头指示法是由源结点将路由信息标识在每个分组的标头中，故又称为源路由法。中转结点交换机根据分组的标头，可知道将该分组转发到那个端口(链路)。因此每个分组的传送路径在它进入网络之前就必须确定。如图所示，假定分组的路径为ACED，可将这四个结点的编号和相应的链路标识在分组标头域中。被标识的结点和链路的出现顺序，应与分组穿越网络的次序相符。,5.3.1 路由问题概述,一、路由表示法,52,(2)路由表法 每个结点交换机中保持着一个路由表，这个路由表是根据采用的路由选择算法预先或实时地计算出来的，它以表格的形式列出了分组从该结点传送到任意目的结点的路由信息。右图网络各结点的路由表如下图。,路 由 表,53,路由表的简化,为了消除路由表中的重复项目，可以用一个默认路由(“*”)代替所有具有相同“下一站”的项目。默认路由比其它项目的优先级低。下图为使用了默认路由的简化路由表，只有超过一个以上的目的结点有相同的下一结点时才使用默认路由,这样使路由表更简洁从而减小搜索时间。目前广域分组交换网大都采用路由表法实现分组的转发，同时也可以支持标头指示法，下面集中讨论得到最广泛应用的路由表法,大型网络使用路由选择算法来产生路由表。,54,路由表的简化,路由问题就是解决分组交换网中的各结点交换机应该如何进行分组转发的问题，因此有必要先研究网络的拓扑结构。(1)用图表示网络可以用图论中的“图”(Graph)表示一个分组交换网络，图的“顶点”表示网络结点，连接顶点的“边”表示网络链路。例如，网络图G=(V,E)，其中，V是网络结点的集合，E是链路的集合。可用一组链路的有序集(l1,l2,ln)来表示网络的一条有向通路(Path)，该通路称为“分组传送路径”(Route)。因此，所谓“路由算法”或“路径选择算法”，就是指确定分组从它的源点到达目的点的有向传输通路的法则。,二、路由选择算法,55,路由表的简化,考虑下图所示的网络，网络图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,l 6,l 1,l 10,l 4,l 7,l 8,l 5,l 2,l 3,l 9,现在的问题:1)用什么算法来选择合适的路径?2)依据什么信息来做这种选择?3)如何执行这种选择策略?4)怎么评价所选路径的好坏?下面讨论路由选择的一般原理及不同的路由选择策略和算法.,57,一个理想的路由选择算法应满足如下要求：1）算法必须是正确的和完整的。2）算法在计算上应尽可能简单。3）算法要有自适应性。4）算法应具有稳定性。5）算法应是公平的。6）算法应是最佳的。,（2）理想的路由选择算法,正确完整每一个节点交换机中的路由表,都必须给出所有可能的目的节点的下一个节点.沿各交换机中的路由表指示的路由分组一定能到达目的计算机所在的哪个交换机.简单为了减少分组转发处理时延.自适应性网络某节点流量过大或故障算法应该能自动适应改变.,稳定性是指:网络拓扑和通信流量相对稳定的情况下,算法得出的路由也应该相对固定.公平是指:算法应该对所有用户都是平等的.最佳是指:最低的代价来实现路由算法,代价是可以有多个因素比如:链路长度,数据率,链路容量,保密,传输延时等.最佳通常是在某种特定要求下得到的较为合理的选择.实际的路由算法应该接近理想算法,并可能有不同的侧重.,59,路由选择算法是解决如何根据网络拓扑和状态，按照一定的性能准则，计算分组传送路径的问题。路由策略是解决路由的选择能否适应网络拓扑和状态变化的问题。路由选择算法仅是路由策略的一部分。从路由的选择能否随网络的变化而自适应地进行调整变化来区分，路由策略可分为两大类，即非自适应路由选择策略与自适应路由选择策略。非自适应路由选择也叫做静态路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。自适应路由选择也叫做动态路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂。,三、路由策略的分类,60,5.3.2 非自适应路由选择,该方法是在每个结点上保持一张路由表，表上标明去每一个目的结点的分组应从哪条链路进行转发。路由表是在整个系统进行配置时生成的，并且在此后的一段相当时间内保持固定不变。当网络拓扑固定不变并且通信流量相对稳定时，采用该方法是适当的。这种路由选择策略的关键是要算出给定网络中任意两个结点之间的最短路径，然后制作出相应的路由表。,非自适应路由选择主要有：固定路由法、概率路由法和洪泛法。,一、固定路由法,61,Dijkstra 算法,62,整个算法包括以下两个部分：初始化 令N 表示网络结点的集合，先令N1。对所有不在N 中的结点v，写出：,寻找一个不在N中的结点w，其D(w)值为最小。把w加入到N中。然后对所有不在N中的结点v，用D(v),D(w)+l(w,v)中的较小的值去更新原有的D(v)值，即：D(v)MinD(v),D(w)+l(w,v)重复步骤，直到所有的网络结点都在N中为止。,Dijkstra 算法(续),63,用Dijkstra 算法求出的最短路径,以1为根的最短 路 径 树,生成结点1路由 表,64,事先在每个结点设置一个路由表，路由表中给出几个可供选择的输出链路，并且对每条链路赋予一个概率。当一个分组到达该结点时，结点产生一个从0.00到0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。这种方法可使通信流量平衡,平均时延小。,二、概率路由法,65,洪泛法是当结点收到一个不是发给它的分组时，就将该分组转发到所有与此结点相连的链路上(除过分组刚刚离开的那个结点)。洪泛法简单可靠，当网络的通信流量很小时，可使分组的传送时延最小。实际应用中很少采用洪泛法。这是因为洪泛法会导致网络出现拥塞。当然可以采用多种方法来限制分组的数目，一种是限制分组在网络中转发的次数(跳数)；另一种是建立登记表来限制分组再次通过该结点。但这些方法不能根本解决洪泛法引起的多个分组副本占用网络资源的问题。在某些特殊场合，如需要将某种信息迅速扩散到全网各个结点时，洪泛法还是有用的。,三、洪泛法（flooding）,66,自适应路由就是网络结点定期或不定期地根据当时的网络状态调整路由。因此网络拓扑和网络状态信息的获取就成为自适应路由的关键。,5.3.3 自适应路由选择,这种路由选择策略是每个结点定期或不定期地与相邻结点交换网络状态信息。经过多次交换，各结点均可掌握全网的情况，从而根据某种路由算法计算并更新其路由表。在分布式路由选择策略中，最基本的算法有两个：距离向量算法 链路状态算法,一、分布式路由选择策略,67,（1）距离向量算法,68,距离向量算法举例,69,距离向量算法的缺陷及解决方法,无穷计算问题距离向量算法在理论上是能有效工作的，但在实际运用中却有很大的缺陷。特别是它对好消息反应迅速，但对坏消息却反应迟钝。在一个最长路径为N跳的子网中，最多经过N次路由信息的交换，所有结点都会知道新增的链路和结点。而对于坏消息，所有结点慢慢地增加其距离值，直至无穷大时，才发现网络拓扑发生了变化。这就是所谓的“无穷计算问题”。,水平分裂算法水平分裂(split horizon)算法是多种解决无穷计算问题的方法之一。水平分裂算法与距离向量算法工作过程一样，不同之处仅在于：任意结点到结点X的距离如果是从结点Y发送的路由信息中获得的，那么该结点不向Y报告其到x的真实距离(报告的距离值为无穷大)。使用水平分裂法，坏消息以每交换一次路由信息传播一个结点的速度传播，这比不用水平分裂方法要好得多。糟糕的是水平分裂法也有失败的时候。,70,距离向量路由算法存在很大的缺陷，很快被一种全新的链路状态路由（link state routing）算法所替代。链路状态路由算法的思想十分简单，可以分五部分加以描述。每个路由器必须：1）发现它的邻居结点，并获取其网络地址；2）测量到各邻居结点的时延（或代价）；3）组装一个分组通告它刚知道的路由信息；4）将这个分组发送给所有其它网络结点；5）计算到所有其它结点的最短路径。事实上，完整的拓扑结构和所有的链路时延都通过试验测量并发布到网络中每一个结点。各个结点可以用Dijkstra算法来找出它到所有其它结点的最短路径。,（2）链路状态路由算法,71,当一个结点被激活以后，它的第一个任务就是要知道谁是它的邻居，这是通过向每条点到点链路发送特殊的Hello分组来实现的。在另一端的结点应发回一个应答分组，以说明它是谁。所有网络结点的名字必须是全局唯一的。当两个或多个结点通过一个局域网(LAN)连接时，引入一个新的虚拟结点N代表LAN(如下图)。,1）发现邻居结点,72,2）测量链路时延或代价 链路状态路由算法需要每个结点知道它到邻居结点的时延或代价。取得时延值的最直接方法就是发送一个要求对方立即响应的特殊的Echo分组。将测量的往返时间除以2，就可以得到该链路的时延估计值。3）构建链路状态分组 一旦用于交换的链路状态信息收集完毕，下一步就是构造一个包含所有这些状态信息的分组。该分组以发送者的标志符开头，紧跟着是顺序号、寿命和一个邻居结点表。在邻居结点表中，列出所有的邻居结点及相应的链路时延。,链路状态路由算法,73,构造链路状态分组是容易的，难的是何时构建分组。一种方式是定期构建；另一种方式是出现一些重要事件时再构建。下图给出了一个包含6个结点的子网，其时延标在结点连线上，并给出了相应的6个链路状态分组。,构造链路状态分组举例,74,该算法最具技巧性的部分就是如何可靠地发布链路状态分组，避免出现死循环、不可达和其它路由问题。链路状态分组的基本发布方法是利用洪泛方式。为防止结点处理和转发过时的链路状态分组，每个分组引入一个顺序号。当一个链路状态分组到达时，先查看一下该分组是否已收到过。如果是新的，就把它转发到除了输入链路之外的所有链路；否则，则丢弃它。在分组扩散过程中，寿命字段每单位时间递减一次，如果寿命为0，则删除该分组，以保证没有任何分组可以在网络中无限长地存活下去。,4）发布链路状态分组,75,链路状态路由算法规定对所有的链路状态分组都需要应答。由于链路状态分组以洪泛方式扩散，所以每个结点需要构造一个如下图所示的分组处理数据结构，用于确定需要向哪些邻结点转发或应答。发送标志位表示该链路状态分组必须发送给哪些邻结点，应答标志位表示应给哪些邻结点发送应答消息。,分组处理数据结构,76,每个结点获得所有的链路状态分组后，便可以构造整个网络拓扑图，每一链路的两个方向都将标出时延(或代价)值。此时每个结点就可以在本地运行Dijkstra算法，从而确定到达所有目的结点的最短路径(或最小代价路径)，并形成分组转发路由表。链路状态路由算法在实际网络中得到了广泛的应用，如在Internet中应用广泛的OSPF协议使用的就是该算法。另一个使用该算法的重要协议是IS-IS协议，该协议应用于多种Internet骨干网(包括老的NSFNET骨干网)，和一些数字蜂窝系统中。,5）计算新路由,77,集中式路由选择策略的核心是在网络中设有网控中心NCC。NCC负责全网状态信息的收集、路由计算以及路由选择的实现。集中式路由选择策略有多种，这取决于储存在NCC中的网络信息的类型、路由的计算方法以及实现路由选择的技术。集中式路由选择策略的好处是：各个结点不需要进行路由选择计算，容易得到精确的路由最优化。还可对进入网络的通信流量实施某种控制。集中式路由选择策略的缺点是：在离NCC较近的地方通信流量的开销较大。更严重的是可靠性问题。一旦NCC出故障，则整个网络即失去控制。,二、集中式路由选择策略,78,从原则上讲，在一个网络中可以混合使用不同类型的路由选择策略。这时只要在每一个结点明确定义出：对于何种类型的通信业务、负荷以及网络的连通条件，应当采用何种的路由选择策略。出于多种考虑，可行的混合式路由选择策略只能是集中式和局部分布式结合起来。集中式的路由选择策略用来寻找在稳定状态下的最佳路由，然后由NCC将路由表送到每一个结点去。而局部的路由选择策略则用来提供对局部的拥塞和故障的迅速响应。这种响应只是暂时的，因而并不要求很精确。不需要多长时间NCC就会发现通信流量以及网络拓扑的变化情况，于是就会对路由表进行更新。,三、混合式路由选择策略,5.4 分组交换性能分析,衡量分组交换设备性能的主要指标是交换时延(Delay)和吞吐量(Throughput).研究的主要数学工具是概率论和排队论。,一、分组交换节点的分析模型,节点交换机或者路由器，是一种多输入多输出的设备，各输入端口首先接受并暂存到来的分组，识别和分析分组的首部，然后根据其中的目的地址查找路由表，从而得知该分组应该转发给那一个下一节点。最后将分组转移到相应的输出端口。分组到达是随机的，在一个输出端口发送一个分组的时间内可能有两个或以上的输入分组同时转移到哪里，从而引起输出链路占用的竞争。解决这个问题采用分组缓冲器，发生冲突的情况下只发送其中一个分组，其余分组在缓冲器内排队等待。,上图为分组输出排队的模型，它是一个随机服务系统，服务对象是分组，分组进入缓冲器排队，然后逐个的服务，服务完后离开系统，它的特点是输入不是单一分组流，而是多个分组流叠加的合成分组流这样的系统分组很困难，为了简化分析要做一些假设。1）各个分组统计独立2）各输入端口到达的分组流式泊松过程，服从泊松分布3）输入端口到达的分组均匀地转移到各输出端口,经过简化分组排队模型变成单输入单输出排队模型。这里分组平均到达速率，任一给定时刻分组缓冲器内等待分组数Q，一个分组需要等待的时间TQ，服务器对分组服务时间TS，分组的服务率(离去率)(输出链路速率)，系统内逗留的分组数N，分组在系统内逗留时间T。和分别是分组平均达到速率和平均服务速率有相同的单位bit/s这些参数都是随便变量分组到达过程为泊松过程的条件下来定量分析,假定分组到达过程为泊松过程，对每个分组服务时间TS相互独立且服从相同的一般分布，供排队的缓冲器容量无限大，服务规则为先来先服务(FIFO)，这样得到M/G/1排队模型。最后我们介绍一下结论：系统内逗留的平均分组数(系统平均对长)：EN=+（2B2+2）/2(1-)B2是系统服务时间的方差，=/是业务量强度系统平均时延：ET=1/+（2B2+2）/2(1-)平均排队队长：