通信網絡基礎總復習第一章通信網絡概論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