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