通信网络基础期末考试总复习

通信网络基础总复习第一章通信网络概论1.1通信网络的基本构成1.2协议体系及分层的概念1.3通信网络的基本理论问题1.1通信网络的基本构成引言1.基本通信网络的构成一个基本的通信网络通常由用户通信终端、物理传输链路（通道）和链路的汇聚点（网络节点）组成。2.通信网络的分类3.常用通信网络1.1.1数据传输链路1.1.2数据传输网络1.1.3网络的互联SimplifiedCommunicationsModel–Diagram(简化的通信模型)2.通信网络的分类用户类型：移动或固定业务的种类：电话、多媒体、计算机数据传输链路或媒介：有线、光纤、无线节点采用的技术体制：ATM交换体制、电路交换体制、分组交换体制应用领域：固定电话网、移动通信网、ATM网络、局域网、民用通信网、军用通信网、专用通信网3.常用通信网络当前通信网络通常由多种不同类型的网络互联互通而构成。主要包括的网络（常称为子网）：ATM(asynchronoustransfermode,异步传输模式)X.25分组数据网PSTN(publicswitchedtelephonenetwork,公用电话交换网)/ISDN(integratedservicedigitalnetwork,综合业务数字网)移动通信网/微型通信网FDDI(fiberdistributeddatainterface,光纤分布式数据接口)环网局域网及高速骨干核心网1.1.1数据传输链路1.概念：所谓数据传输链路是指在物理传输媒介（如双绞线、同轴电缆、光纤、微波传输系统、卫星传输电路等）上利用一定的传输标准（它通常规定了电气接口、调制解调方式、数据编码的方式、比特同步、帧格式和复分接的方式等）形成的传输规定速率（和格式）的数据比特通道。2.数据传输链路的分类分为两大类：一类是用户到网络节点（路由器或交换机）之间的链路，（简称为接入链路）另一类是网络节点（路由器或交换机）到网络节点（路由器或交换机）之间的链路，（简称为网络链路）接入链路接入链路有多种形式：如Modem（调制解调器）链路、xDSL链路、ISDN链路、无线链路（移动通信和卫星通信链路）、局域网链路等Modem链路：利用传统PSTN的电话线路，在用户侧和网络侧分别添加Modem设备来实现数据传输，传输速率可为300b/s到56kb/sxDSL链路是通过数字技术，对PSTN端局（本地电话交换机）到用户终端之间的线路进行改造而成的数字用户线DSL（DigitalSubscriberLine）。DSL的前缀x表示不同的传输方案。例如：ADSL（AsymmetricDSL，非对称数字用户线）的上行速率为640kb/s~1Mb/s，下行速率为6~8Mb/s;HDSL(HighSpeedDSL)上下行速率相同，均为768kb/s或1.5Mb/s；VDSL(VeryhighSpeedDSL)下行速率12.96Mb/s、25Mb/s、52Mb/s,上行速率为1.6~2.3Mb/sISDN链路：利用传统的电话线路实现数据传输，提供两个基本信道：B信道(64kb/s)和D信道(16kb/s或64kb/s)。无线链路中最典型的链路是数字蜂窝移动通信链路，根据使用的空中接口标准（如：GSM、IS-95、IMT-2000）的不同，支持的数据传输速率为十几kb/s到几Mb/s。对于卫星链路，根据星座结构和卫星数目的不同，支持的数据传输速率从几kb/s到几百kb/s。如果采用短距离的无线接入技术（如无线局域网）其速率可达几十Mb/s至几百Mb/s。新一代的移动通信系统和新一代的无线局域网将提供1Gb/s以上的数据传输速率。局域网链路中最典型的是以太网（Ethernet）链路，在双绞线上可传输的的峰值数据速率为10Mb/s、100Mb/s、1000Mb/s。是在办公室环境下，最常用的接入方式。网络链路网络链路也有多种形式：如帧中继、SDH、WDM等。SDH（SynchronousDigitalHierachy,同步数字体系）是在美国贝尔实验室提出的SONET（SynchronousOpticalNetwork,光同步数字体系）的基础上指定的技术标准，它具有一套标准化的结构等级STM-N（N=1,4,16,64）,它们的传输速率分别为STM-1（155.52Mb/s），STM-4（622.08Mb/s），STM-16（2488.32Mb/s），STM-64（9953.28Mb/s）WDM（WaveLengthDivisionMultiplexing,光波分复用）技术是在一根光线中同时传输多个波长光信号的一种技术。在发端将不同波长的光信号组合（复用）起来。在接收端又将组合的光信号分开（解复用）并送到不同的终端。目前在一根光纤上可提供的数据速率为4*2.5Gb/s（第一个数字4为波长书，第二个数字为每一波长上的速率）、16*10Gb/s，160*2.5Gb/s、128*10Gb/s等，理论上可达5Tb/s的传输速率。A.分组交换网1.基本概念在分组交换网中，将消息分成许多比较短的格式化的数据块称为分组（Packet）进行传输和交换。每一个分组由若干比特的数据组成。每一个分组通常包括一个附加的分组头。分组头指明该分组的目的节点及其他网络控制信息。在每一个网络节点中采用存储转发的工作方式来将输入的分组送到选定的输出链路上。（这种按照一定的规则（路由算法）将输入分组送到选定的输出链路上的过程称为交换）。分组交换网如图1-3所示如何选择一条合适的传输路径？2.选择路由方式主要有两种基本的选择路由方式虚电路方式数据报方式虚电路方式在虚电路方式中，在一个会话过程开始时，确定S到D的一条逻辑通路（即实际分组传输时才占用物理链路，无分组传输时不占用物理链路。此时物理链路可用于其它用户分组的传输）。会话过程中，所有的分组都沿此逻辑通道进行。如上图的S到D之间为消息A建立了一条逻辑通路。每一条逻辑通路中的逻辑链路可用一个虚电路号（VCn）来表示数据报方式在数据报方式中，为会话过程中的每一个分组独立地选择路由，也就是S到D之间一次会话过程中的分组可以独立地选择路径A、B、C或其他路径。因而，到达目的节点D的分组所经过的链路可能各不相同。B电路交换电路交换（或称线路交换）是指根据用户的呼叫请求，将输入物理电路直接与输出物理电路相连接的一种交换技术。在电路交换网络中，在双方通信之前，需要在对方建立一条直接的物理通路，在通信结束后，要拆除该物理通路。在通信过程中，收发双方独占该物理通路。在电路交换方式中，信息的传输具有很短的时延，且可以保持收房双方严格的同步关系。但与分组交换相比，链路使用效率相对较低。C.ATM网络ATM(AsynchronousTransferMode)是在传统电话网使用的电路交换以及分组交换网基础上发展起来的一种交换技术，可以较好地支持不同速率、不同种类的宽带信息交换。它与分组交换的差别是采用一个全网统一的固定长度的分组（称之为信元）进行传输和交换。ATM网络中，信元的长度为53个字节，其中5个字节为信元头，48个字节用来运载信息。好处：由于信元长度和格式固定，可用硬件电路对信元进行处理，因而缩短了每一个信元的处理时间。ATM采用面向连接（即虚电路）方式，以提高信息传输的实时性。ATM设计是以光纤传输为基础，因此在传输链路上采用了非常简单的差错控制和流量控制等措施，提高了在网络中的传输速率。ATM信元格式ATM信元格式：UNI接口和NNI接口的信元格式除前12个比特格式不同外，其余格式完全相同。GFC（GenericFlowControl）是流量控制比特VPI/VCI

用来表示信元传递的路径。其中，VPI(VirtualPathIdentifier)是虚通道标识，VCI(VirtualChannelIdentifier)是虚通路标识。PT(PayloadType,负荷类型)用来区分该信元是用户信息还是控制信息CLP(CellLossPriority,信元丢失优先级)指示信元丢失的优先级HEC(HeaderErrorControl,信元头差错控制)提供信元头四个字节的差错控制，可用于多个比特的检错和单个比特的纠错。ATM网络的服务ATM信元通常是在SDH链路上进行传输为了支持不同类型的业务，ATM网络向用户提供四种类别的服务，即A类、B类、C类和D类。服务类别是根据业务的比特率是固定的还是可变的、源节点到目的节点是否需要同步、以及是面向连接还是无连接来划分的。对于不同类别的业务，ATM网络采用不同的适配方法（即如何将业务比特流分段，形成协议数据单元CS-PDU），再如何将CS-PDU分成信元，最后如何有效地传输这些信元。这些适配方法称为AAL1~AAL5。AAL1支持A类：恒定比特率、收发需要定时关系、面向连接的业务。AAL2支持B类：可变比特流、收发需要定时关系且面向连接的业务（如话音和图像等业务）AAL3/4支持C类/D类业务：服务既可以是面向连接的也可以是无连接的，支持的业务可以是报文模式也可以是流模式。AAL5为面向连接的应用提供更为有效的运载措施1.1.3网络的互联前面两个小节主要讨论的是一个子网内的问题，这时所有的链路具有相同特性，采用某种数据传输链路协议和寻址方式，通过交换设备来实现子网内的路由选择和信息交换。当多个（不同传输和交换方式的）子网要互联互通构成一个大的网络时，需要采用路由器（设备）。如图1-5所示全网互联的基本条件为实现全网互联需要两个基本条件：一是全网统一编址，二是路由算法。编址解决如何区分网络中的节点、用户终端等，例如在Internet中是采用IP地址来区分路由器、服务器、用户计算机等。路由算法解决从源到目的地之间应经过的子网、路由器、网络节点等。例如，可以采用从源到目的地经过的路由器最少的原则来选择一条路由。习题1.11.21.31.41.51.81.2协议体系及分层的概念1.2.0通信协议的重要性1.2.1分层的概念1.2.2OSI协议体系结构1.2.3TCP/IP协议体系结构1.2.4混合的分层协议1.2.1分层的概念通信网络的协议可按照分层的概念来设计。分层概念的基础是“模块”的概念模块提供的功能通常称之为服务。相邻层间的服务是通过其接口面上的服务访问点（SAP）进行的3.网络协议为实现网络中的数据交换建立的规则标准或约定，它主要由语法、语义和时序三部分组成，即网络协议的三要素ProtocolDataUnits(PDU)（协议数据单元）在每一层，使用协议进行通信在每一层要向用户数据中加入控制信息运输层可能将用户数据分割成小块每一个小块加入一个运输层首部DestinationSAP（目的服务访问点）Sequencenumber（序号）Errordetectioncode（差错检测代码）构成一个运输层PDUNetworkPDU（网络层PDU）Addsnetworkheader（加入网络层首部）networkaddressfordestinationcomputer（目的计算机地址）Facilitiesrequests（功能请求）1.2.2OSI协议体系结构OpenSystemsInterconnection（开放系统互联）国际标准化组织（ISO）将协议体系结构分为七个层次：应用层、表示层、会话层、运输层、网络层、数据链路层和物理层，并将它作为开发协议标准的框架。该模型被称为开放系统互联参考模型OSI，如图1-9。1.2.3TCP/IP协议体系结构TCP/IPProtocolArchitecture(1)ApplicationLayer（应用层）负责进程或应用之间的通信Endtoendortransportlayer(TCP/UDP/…)（主机对主机层或运输层）端到端的数据传输包括两种不同的协议：TCP和UDP。TCP为应用程序之间的数据传输提供可靠连接，它是面向连接的传输控制协议。UDP为应用层提供无连接的尽力服务，它并不保证一定传到，也不保证按顺序传输以及不重复传送。TCP/IPProtocolArchitecture(2)InternetLayer(IP)（互联网层）如果两台设备连载两个不同的网络上，要是数据穿过多个互联的网络正确地传输，是互联网层（网际层）的功能。数据的路由选择与IP一起工作的还有ICMP（InernetControlMessageProtocol）、ARP(AddressResolutionProtocol)、RARP(ReverseARP)等协议NetworkaccessLayer（网络接入层）端系统与其连接网络之间的逻辑接口PhysicalLayer（物理层）Transmissionmedium（传输媒体）Signalrateandencoding（信号速率及编码）第二章端到端的传输协议主要内容2.1组帧技术2.1.1面向字符的组帧技术2.1.2面向比特的组帧技术2.1.3采用长度计数的组帧技术2.2链路层的差错控制技术2.2.1流量控制2.2.2差错检测2.2.3ARQ协议1.停等式ARQ停等式ARQ（Stop-and-WaitARQ）基本思想是在开始下一帧传送以前必须确保当前帧已被正确接收。StopandWait（停止等待ARQ）Sourcetransmitssingleframe（源点传输一个帧）WaitforACK（等待确认）Ifreceivedframedamaged,discardit（如果接收到的帧被损坏，则丢弃）Transmitterhastimeout（源点设置了一个计时器）IfnoACKwithintimeout,retransmit（如果计时器超时而没收到确认，则再次发送同一个帧）IfACKdamaged,transmitterwillnotrecognizeit（如果确认损坏，发送站点无法辨认）Transmitterwillretransmit（发送站点将重传）Receivegetstwocopiesofframe（接收站点收到两份同一帧的副本）UseACK0andACK1（为避免混淆，帧被交替标记为0和1，肯定确认的格式则为ACK0和ACK1）StopandWait-

DiagramStopandWait-ProsandConsSimple（简单）Inefficient（低效率）2.返回n-ARQGoBackNBasedonslidingwindow（基于滑动窗流量控制）Ifnoerror,ACKasusualwithnextframeexpected（如果没有差错，确认里面包含希望收到的下一帧的序号）Usewindowtocontrolnumberofoutstandingframes（使用窗口来控制收到确认前允许发送的帧数）Iferror,replywithrejection（如果发现差错，则会为这个帧发送一个否认）Discardthatframeandallfutureframesuntilerrorframereceivedcorrectly（丢弃该帧及该帧以后的帧，直到接收到正确的该帧）Transmittermustgobackandretransmitthatframeandallsubsequentframes（发送端必须返回并重传出错的帧及其以后的帧）GoBackN-

Diagram3.SelectiveReject（选择拒绝）Alsocalledselectiverepeat（又称选择重发式ARQ）Onlyrejectedframesareretransmitted（只有被拒绝的帧被重传）Subsequentframesareacceptedbythereceiverandbuffered（接收端收到后继帧并缓存下来）Minimizesretransmission（将重传帧的数量减到最低）Receivermustmaintainlargeenoughbuffer（接收端必须维护足够大的缓存）Morecomplexlogicalintransmitter（在发送端具有更复杂的逻辑）SelectiveReject-

Diagram

ThefollowingfiguresshowtheerrorcontrolmechanismsbyGo-back-NARQandSelective-rejectARQ.StationAissendingframestostationB.Thewindowsizeisalllimitedto8.Thefirsttransmittedframearegiventoyou,pleasefilltheotherframesintheblanksbesidethefigure.

2.3标准数据链路控制协议及其初始化2.3.1标准的数据链路控制协议2.3.2数据链路层协议的初始化标准DLC协议的帧结构（1）FlagFields（标志字段）Delimitframeatbothends（在帧的两端起定界作用）01111110（采用01111110模式）Maycloseoneframeandopenanother（可以是一帧的结束标志同时是下一个帧的起始标志）Receiverhuntsforflagsequencetosynchronize（接收方不断搜索标志序列用于一个帧起始时的同步）Bitstuffingusedtoavoidconfusionwithdatacontaining01111110（用比特填充来避免标志字段和带有01111110的数据的混淆）AddressField（地址字段）Maybeextendedtomultiplesof7bits（可扩展为7比特的倍数）LSB（最低位）ofeachoctet（八位组）indicatesthatitisthelastoctet(1)ornot(0)Allones(11111111)isbroadcast控制字段Controlfield(控制字段)S帧U帧例2.3NRM（主从式）的工作过程例2.3NRM（主从式）的工作过程在NRM工作过程中，地址域总是从站的地址，主站在发出命令和数据时，使用从站的地址，从站用自己的地址予以响应或传输数据上图分为三个过程：A与B建立连接，A和B同时传输数据和A拆除连接。在这些过程中，任何一方发送数据和要求对方应答时使用对方的地址，应答时使用自己的地址。InformationField（信息字段）Onlyininformationandsomeunnumberedframes（只有I帧和某些U帧才有信息字段）Mustcontainintegralnumberofoctets（必须由整数个八位组组成）Variablelength（长度不固定）第四章多址接入协议

4.1多址协议概述4.2固定多址接入协议4.3随机多址接入协议4.4预约多址接入协议主要内容MAC层在通信协议中的位置从分层协议体系的角度看，多址技术实际上是在数据链路层上实现的。将与之对应的层次称为多址接入控制子层MAC（MediumAccessControl）MAC层处于数据链路逻辑控制子层LLC（LogicalLinkControl）下方，物理层上方。LLC层为本节点提供到其邻节点的链路，而MAC层的主要功能是协调本节点和其他节点有效地共享带宽资源。MAC层在通信协议中的位置多址协议的分类根据对信道的使用情况，分为三类：固定分配多址协议随机分配多址协议基于预约方式的多址协议固定分配多址协议所谓固定分配多址协议是指在用户接入信道时，专门为其分配一定的信道资源（如频率、时隙、码字或空间），该用户独享该资源，直到通信结束。由于用户使用该资源时不和其他用户发生冲突。因此，也称为无冲突的多址协议。典型的固定多址方式有：频分多址（FDMA）、时分多址（TDMA）、码分多址（CDMA）、空分多址（SDMA）等。随机多址协议所谓随机多址协议是指用户可以随时接入信道，并且可能不会顾及其他用户是否在传输。当信道中同时有多个用户接入时，在信道资源的使用上就会发生冲突（碰撞）。因此，随机多址协议也称为有竞争的多址协议。对于这类协议如何解决冲突从而使所有碰撞用户都可以成功进行传输是一个非常重要的问题。典型的随机多址协议有：完全随机的多址接入协议（ALOHA协议）和基于载波侦听的多址协议（CSMA协议）基于预约的多址协议所谓基于预约的多址协议，是指在数据分组传输之前，先进行资源预约。一旦预约到资源（如频率、时隙等）则在该资源内可进行无冲突的传输。如基于分组的预约多址协议PRMA（PacketReservationMultipleAccess），其基本思想是首先采用随机多址协议来竞争可用的空闲时隙，若移动台竞争成功，则它就预定了后续帧中相同的时隙。在后续帧中，它将不会与其他移动台的分组发生碰撞。预约多址接入协议前面介绍的随机多址接入技术共同的关键技术是如何最大限度地减少发送冲突，从而尽量提高信道利用率和系统吞吐量。预约多址协议的要点是最大限度地减少或消除随机因素，避免发送竞争带来的对信道资源的无秩序竞争，使系统能按各节点的业务需求合理地分配信道资源。所以，预约方式有时又被称为按需分配方式。第五章路由算法ExamplePacketSwitchedNetwork

路由选择策略固定式路由选择（Fixed）洪泛式路由选择（Flooding）随机路由选择（Random）自适应路由选择（Adaptive）固定式路由选择固定式路由选择为网络中的每一对源节点和目的节点选择一条永久的路由。这些路由是固定的，只有在网络拓扑结构发生改变时，它们才有可能改变因此，在设计路由时所使用的链路代价不可能是基于通信量的动态改变需要创建一个中心路由选择矩阵，它可能保存在网络的控制中心。该矩阵指出每一对源节点和目的节点的路由途中的下一个节点标识每一个节点只需要保存路由表的一列固定

路由

选择使用固定路由选择，数据报和虚电路在路由选择时没有区别。从指定源节点到指定目的节点的所有分组都沿相同的路由前进。固定路由选择的优点是它的简洁性，并且在一个具有稳定负荷的可靠网络中表现良好。其缺点在于缺乏灵活性，无法对网络拥塞或故障做出反应。洪泛式路由选择这种技术不需要任何网络信息，其工作过程如下：一个分组由源节点发送到与其相邻的每一个节点上在各个节点上，收到的分组再次被传输到除分组到达时所经过的链路外的所有输出链路。最终会有几分这个分组的副本到达目的节点这个分组必须具有某种唯一性的标识（如源节点和序号，或许电路号和序号）以便目的节点保留所收到的第一份副本，而丢弃其他副本。为防止分组在网络中无穷无尽地传输，也可以让节点记住所重传过的那些分组的标识，当该分组的副本再到达时被丢弃；或者在每个分组中包含一个跳数计数器字段，每次节点向前传输一个分组时，将该分组计数器值减一，当计数器值为零时，该分组被丢弃。洪泛式路由选择洪泛式技术的特点洪泛式技术具有三个重要属性：在源点和终点之间的所有路由都被尝试过非常稳健可用于发送紧急报文因为所有路由都被尝试过，因此分组至少有一个副本使用的是最小跳数路由到达终点可用于虚电路路由的最初建立所有直接或间接与源节点相连的节点全部被访问到对于某些向所有节点散播的重要信息来说十分有用，被用于某些路由选择策略的信息发布机制中随机路由选择使用随机路由选择时，为了重传收到的分组，节点只选择一条输出链路。这条链路是从除了分组到达时所经过的那条链路之外的其他链路中随机选取的。如果所有链路被选中的可能性都相等，那么节点可能会简单地以轮流方式使用输出链路。改良方法是为每条链路分配一个概率，并根据概率来选择链路。这个概率可以基于数据率或固定链路代价的。与洪泛式一样，随机路由选择不需要使用网络信息。因为采取什么路由是随机决定的，所以实际的路由往往既不是最小代价路由也不是最小跳数路由自适应路由事实上，所有分组交换网络中，都使用了某种形式的自适应路由选择技术。即路由选择的判决随网络条件的变化而改变。影响路由选择判决的主要条件有：Failure（故障）Congestion（拥塞）要使自适应路由选择成为可能，就必须在节点和节点之间交换有关网络状态的信息。5.4最小代价算法所有分组交换网络的路由选择判决都是基于某种形式的最小代价标准如果这个标准取得是最小跳数，那么每条链路具有的值都是1更常见的情况是链路的值与链路容量成反比，与链路当前负荷成正比，或是这两者的结合。最小代价算法可描述如下：假设一个网络节点由双向链路连接，其中每条链路的各个方向上都有一个相关的代价，并且定义两个节点之间的路径代价为途径的链路代价的总和。对于每一对节点找出具有最小代价的路径。需要注意的是：一条链路在两个方向上的代价可能不同。5.4.1Dijkstra算法Dijkstra算法思路如下：通过拓展路径以不断增加这条路径的长度，从而寻找给定源节点到所有其他节点之间的路径。该算法分阶段进行：在第k阶段，已经判断出k个离源节点最近的（它们之间的代价最小）节点具有的最短路径，这些节点在集合T中。在第k+1阶段，不在T中但具有到源节点最短路径的节点被加入到T中。当每个节点加入T时，就定义了它与源节点之间的路径。算法中变量N：网络中的节点集合s：源节点T：目前由算法合并的节点集合w(i,j)：节点i到j之间的链路代价w(i,i)=0w(i,j)=

如果两节点之间不是直接连接的w(i,j)0如果两节点之间是直接连接的L(n)：算法目前所知从节点s到节点n的最小代价路径的代价算法结束时，就是从节点s到节点n的最小代价路径的代价Dijkstra算法Step1初始化T={s}目前的节点集合只有源节点L(n)=w(s,n)forn≠s相邻节点的初始路径代价就是链路代价Step2找到下一个节点从不属于T的相邻节点中找到到源节点路径代价最小的节点x将该节点x合并到T中向T加入一条边，这条边恰好在x上，且在L(x)中加入最小代价元素Step3更新最小代价路径L(n)=min[L(n),L(x)+w(x,n)]forallnÏT如果后一项较小，则从s到n的路径变为从s到x的路径与从x到n的链路衔接） 循环step2-step3，当所有节点都已经加入T后算法终止Dijkstra’sAlgorithmNotes结束时，与各节点x相关的值L(x)是从s到x的最小代价路径的代价）T定义了从s到各节点的最小代价路径第2步和第3步每循环一次就向T中加入一个新节点并定义了从s到该节点的最小代价路径

ExampleofDijkstra’sAlgorithmResultsofExampleDijkstra’sAlgorithm5.4.2Bellman-Ford算法B-F算法可叙述如下：从给定的源节点找出一条最短路径，该最短路径是从所有最多只含一条链路的路径中选择出来的；接着再找出条件为所有路径最多只含两条链路的最短路径，以此类推。

算法也是分阶段进行。定义变量如下：s：源节点w(i,j)：节点i到节点j之间的链路代价w(i,i)=0w(i,j)=

如果两节点不是直接连接的w(i,j)0如果两节点是直接连接的h：算法当前阶段中的路径具有的最大链路数Lh(n)：在不多于h条链路的条件下，从节点s到节点n的最小代价路径的代价Bellman-Ford算法Step1初始化L0(n)=,forallnsLh(s)=0,forallhStep2更新对每个后继的h0对每个n≠s,计算Lh+1(n)=minj[Lh(j)+w(j,n)]将n与前一次处理的节点j相连接，以获取最小值删除在以前循环时形成的n与任何其他前次处理节点之间的连接从s到n的路径以从j到n的链路结束Bellman-FordAlgorithmNotes第二步中当h=K，并且对每个目的节点n，算法将从s到n的长度为K+1的可能路径与前一次循环结束时得到的路径相比较如果前次更短路径具有较小代价，则仍保持前次路径否则，从s到n之间定义一条长度为k+1的新路径ExampleofBellman-FordAlgorithmResultsofBellman-FordExample

第六章拥塞控制6.2拥塞控制机制6.2.1Backpressure（反压）如果某节点发生拥塞，它会减慢或组织从其它节点来的流量这意味着其它节点也会控制本身入口链路上的输入分组通信量这种流量限制将反向传播到信源可有选择地应用到通信量最大的某些逻辑连接上适用范围有限：可用于允许使用逐跳流量控制的面向连接的网络，e.g.X.25无法在ATM和帧中继中使用OnlyrecentlydevelopedforIP6.2.2ChokePacket（阻流分组）阻流分组是由拥塞的节点产生的控制分组，被传回到源节点抑制通信流量e.g.ICMP

sourcequench（Internet报文控制协议的“源点抑制”分组路由器或目的端系统都可以向源端系统发送此报文一旦接受到一个源点抑制报文，源点主机将会降低它对特定终点的发送速率，直到不再接收到源点抑制报文为止当路由器或主机由于缓存溢出而不得不丢弃IP数据报时，它会为每个丢弃的数据报发送一个源点抑制报文；或者当一个系统的缓存将满时，它可能会预测到拥塞的发生，因此而发送源点抑制报文阻流分组是一种比较粗糙的拥塞控制技术6.2.3ImplicitCongestionSignaling（隐式拥塞信令）网络发生拥塞时，可能会出现两种情况：从源点到终点的的个别分组的传输时延加大，以至于明显比固定传播时延长得多分组被丢弃如果源点能够检测到传输时延的增加以及分组的丢弃就将这些作为发生拥塞的症状，然后减缓流量。因此，基于隐式信令的拥塞控制是由端系统完成的，并且不需要网络节点的参与。在数据报分组交换网和基于IP的互联网这样的无连接或数据报的配置中，隐式拥塞信令是一种有效的拥塞控制技术e.g.IPbased(TCPincludescongestionandflowcontrol-seechapter17)隐式拥塞信令也可用于面向连接的网络，如，帧中继中的LAPF控制协议就包含了类似TCP流量和差错控制的机制。LAPF控制可以检测到帧丢失，并据此调节数据流量6.2.4ExplicitCongestionSignaling（显式拥塞信令）希望网络中的可用容量都能得到充分利用，同时又能够以公平的方式对拥塞做出及时地反应以控制拥塞。这是显式拥塞信令技术的目标。实现：由网络对正形成的拥塞向端系统发出警告，端系统则采取措施降低对网络的供给负荷。通常显式拥塞信令技术用于面向连接的网络中，并以单个连接为单位控制分组流量显式拥塞信令可以向两个方向发送：Backwards（反向）告知源点应该对与收到分组方向相反的方向上的通信量采取拥塞避免措施。它表示用户在该逻辑连接上传输的分组可能会遭遇拥塞的网络资源。Forwards（前向）通知用户应该对与收到分组方向相同的通信量采取必要的拥塞避免措施。它表示这个分组在其逻辑连接上遭遇了拥塞的网络资源。显式拥塞信令的分类Binary（二进制的）拥塞节点在转发数据分组时对分组中的某一比特位置位Creditbased（基于信用值的）在一条逻辑连接上对源点提供显式信用值。这个信用值表示了允许源点发送的字节数或分组数，当一个源点用完了它的信用值后，必须等待更多的信用值才能发送更多的数据在端到端的流量控制中常见Ratebased（基于速率的）在一条逻辑连接上提供一个明确的数据率上限，源点只能以不超过该上限的速率发送数据。逻辑连接上任何一个节点都可减少发往源点的控制分组中的数据率上限值来控制拥塞e.g.ATM6.3通信量管理发生拥塞时最简单的办法是丢弃分组，当不得不丢弃分组时，拥塞控制技术和丢弃规则应当考虑以下因素公平性：希望不同的流量在遭受拥塞方面能体现出公平性服务质量希望用不同的方法对待不同的通信流量预留避免拥塞并对一些应用提供确保服务的一种方法是采用预留（reservation），这种方式是ATM网络中的一部分。当要建立一条逻辑连接时，网络和用户就订立了一个通信量合约，在其中指明通信流量的数据率和其他特性参数。只要通信流量在合约参数规定范围内，网络就向其提供事先商定好的服务质量；超过合约规定的通信量要么被丢弃，要么以尽最大努力传送的方式处理6.5.1通信量速率管理帧中继网络解决拥塞的最后办法是丢弃帧最简单的办法是随意丢弃一些帧，而不管帧的来源这样对流量进行限制没有效果，所以对端系统个体来说，最好的策略是尽快的传输帧为了较公平的分配资源，帧中继承载业务包含了许诺信息速率（CIR）的概念CIR是网络认同的用于支持某个特定帧方式连接的速率，单位bps任何以超过CIR速率传输的数据在发生拥塞时最容易被丢弃尽管使用了许诺这个术语，但并不保证提供的服务速率一定能够达到CIR理论上讲，与某个节点相连的所有端系统的所有连接的整体CIR不超过节点的容量；整体CIR也不应超过用户网络接口上的物理数据率，即接入速率CommittedburstsizeBc（许诺的突发数据长度）：在测量间隔T内网络同意传输的最大数据量ExcessburstsizeBe（过量突发数据长度）：在测量间隔T内网络试图传输的超过Bc的最大数据量（T=Bc/CIR）CIR的工作原理拥塞参数之间的关系说明6.5.2使用显式信令的拥塞避免显式拥塞避免就是由网络向端系统警告网络拥塞正在增长的情况，由端系统采取措施减轻提供给网络的负载量帧的地址字段需要为显式信令提供两个比特，这两个比特可以由任何探测到拥塞情况的帧处理器置位BECN，反向显式拥塞指示：通知用户应当激活拥塞避免过程，它对与接收帧相反方向上的通信量起作用FECN，前向显式拥塞指示：通知用户应当激活拥塞避免过程，它对与接收帧方向相同的通信量起作用网络响应每个帧处理器都必须监视它的队列行为，如果队列长度开始增长到某个危险水平，那么帧处理器就将FECN或BECN置位帧处理器需要确定应当警告哪一条逻辑连接。如果拥塞非常严重，则通过该帧处理器的所有逻辑连接都可能被警告；在拥塞早期，可能仅警告产生最大通信量的连接所对应的用户用户响应用户响应由收到的BECN和FECN信令决定：最简单的是对BECN的响应：用户简单地降低帧传输速率直到该信令取消为止；对FECN的响应较复杂，因为需要用户向该连接上的对等用户发出指示，以限制帧通信量。帧中继协议的核心功能不支持这种指示功能，必须通过高层如运输层来完成。流量控制也是通过位于帧中继子层之上的LAPF控制协议或其它链路控制协议来实现6.6.4通信量和拥塞控制框架结构ObjectivesofATMlayertrafficandcongestioncontrol:ATM通信量和拥塞控制应当支持一组能够满足各种可预测的网络服务的ATM层服务质量类型不能依赖于具体网络服务相关的AAL协议，也不能依赖于具体的应用相关的上层协议

需要尽量提高网路利用率的同时，尽量降低网络和端系统的复杂性TimingsConsidered为实现上述目标，itu-t定义了一组通信量和拥塞控制功能的集合，其操作跨越多种时间尺度，这些功能从时间上考虑可分为四级）Cellinsertiontime（信元插入时间）Roundtrippropagationtime（往返传播时间）Connectionduration（连接时间）Longterm（长期）通信量控制策略的本质基于判断是否能够容纳一条约定的新ATM连接与用户协商需要支持的性能参数6.6.5通信量管理和拥塞控制技术ATM通信量管理功能指的是网络采取的一组动作，用以避免拥塞或尽量减少拥塞后果使用虚通道进行资源管理连接许可控制使用参数控制选择性信元丢弃通信量整形1.使用虚通道进行资源管理网络资源管理是指以某种方式分配网络资源，即按照不同的服务特性来区分不同的通信流量网络在虚通道上提供综合的容量和性能特性，需要考虑三种情况Usertouserapplication（用户到用户的应用）Usertonetworkapplication（用户到网络的应用）Networktonetworkapplication（网络到网络的应用）网络资源管理主要关心的Qos参数Celllossratio（信元丢失率）Celltransferdelay（信元传送时延）Celldelayvariation（信元时延偏差）Configuration（配置）ofVCCsandVPCsAllocatingVCCswithinVPC（VPC内VCC的容量分配）AllVCCswithinVPCshouldexperiencesimilarnetworkperformanceOptionsforallocation（网络在向VPC分配容量的选项）Aggregatepeakdemand（聚集峰值需求）Statisticalmultiplexing（统计复用）2.

连接许可控制是网络防止自己超载的第一道防线当用户请求一条新的VPC或VCC时，必须为这条连接的两个方向定义通信量特性用户通过从网络提供的Qos类型中选择一个Qos来选定通信量的特性只有当网络在能够维持原有连接的协商Qos的同时还能够提供必要的资源来支持这个通信量级别时，网络才会接受该连接只要网络接受了这条连接，就说明他与用户之间形成了一份通信量和约通信量合约中的参数Peakcellrate（PCR,峰值信元速率）Celldelayvariation（CDV,信元时延偏差）Sustainablecellrate（SCR,可维持信元速率）（在一条ATM连接的持续时间内计算得到的平均速率上限）Bursttolerance（突发容限）（以持续信元速率为参考，在单个测量点上观测到的信元到达模式中的持续信元速率变化上限）3.使用参数控制Thepurposeofusageparametercontrol:一旦连接许可控制接受了某条连接，网络的使用参数控制就会监视连接保证通信量遵守合约如果有违反合约，则采取适当措施以防止某条连接上网络资源的超负荷对其他连接带来不利影响使用参数控制可以在VPC和VCC两级实现使用参数控制包含两个独立的功能PCR及其相关的信元时延偏差（CDV）控制可维持信元速率（SCR）及突发容限控制UPC算法是通信量管制的一种形式，通信量管制就是调整数据流，将超过一定性能水平的信元丢弃或打上标记4.通信量整形希望有一种通信量整形的的策略作为通信量管制的辅助策略。通信量整形用于平滑通信流量，以减少信元成块堆积的现象，这可以使资源的分配更加公平，并减少平均时延通信量整形的一种简单方法：令牌桶UPC算法只是简单地监视通信量，并丢弃不遵守合约的信元或将他们打上标记；与此相反，通信量整形令牌桶则控制的是遵守合约的信元流用于通信量整形的令牌桶6.7保证帧速率通信量管理从端系统的角度看，它提供了像UBR一样简单的服务从复杂度和额外开销来看对ATM网络元素的要求相对不高端系统在使用GFR时对传输的通信量不进行管制或整形而是以ATM适配器的线速率来传输不保证帧交付如果遇到拥塞引起丢弃帧，应当由上一层通过实施窗口管理和拥塞控制技术来处理和UBR不同的是，允许用户为每个VC预留一定量的容量这些预留容量保证用户应用可以在无丢弃的情况下传输的最小速率如果网络没有拥塞，用户则能以更高的速率传输FrameRec