通信規(guī)程和通信網(wǎng)理論基礎(chǔ)

通信規(guī)程和通信網(wǎng)理論基礎(chǔ)本章主要內(nèi)容8.1網(wǎng)絡(luò)協(xié)議體系結(jié)構(gòu)8.2排隊論基礎(chǔ)8.3通信網(wǎng)拓撲結(jié)構(gòu)8.4最短徑第2頁,共55頁，2024年2月25日，星期天8.1網(wǎng)絡(luò)協(xié)議體系結(jié)構(gòu)8.1.1通信規(guī)程和規(guī)程參考模型8.1.2業(yè)務(wù)原語8.1.3數(shù)據(jù)單元8.1.4開放系統(tǒng)互聯(lián)參考模型8.1.5互聯(lián)TCP/IP參考模型8.1.6標準化組織第3頁,共55頁，2024年2月25日，星期天8.1.1通信規(guī)程和規(guī)程參考模型通信規(guī)程

為進行通信中的數(shù)據(jù)交換而建立的規(guī)則、標準或約定。規(guī)程參考模型

通信規(guī)程有層次特性，大多數(shù)網(wǎng)絡(luò)的組織都按層或級的方式來組織。第4頁,共55頁，2024年2月25日，星期天（N+1）層實體（N）層實體（N-1）層實體（2）層實體（1）層實體N+1層通信實體N+1層通信實體N層實體N層實體N-1層實體N-1層實體實際通信線路N層SAP等效通信線路N+1層N層N-1層用戶用戶（a）N層通信實體級聯(lián)（b）N層通信實體級聯(lián)圖8.1N層規(guī)程參考模型第5頁,共55頁，2024年2月25日，星期天實體(Entity)

在一個計算機系統(tǒng)中，任何能完成某一特定功能的進程或程序，都可稱為一個“實體”。功能層(Layer)

“層”是指系統(tǒng)中能提供某一種或某一類服務(wù)功能集合的“邏輯構(gòu)造”，一個層中可包含一個或多個實體，該層的功能依靠層中的實體執(zhí)行該層的協(xié)議來體現(xiàn)。

協(xié)議(Protocol)

兩系統(tǒng)中對等實體之間密切地協(xié)調(diào)工作所必須遵守的一組預(yù)定規(guī)則和約定，稱為“協(xié)議”。

第6頁,共55頁，2024年2月25日，星期天服務(wù)（Service）及服務(wù)訪問點（SAP）

服務(wù)是網(wǎng)絡(luò)的低層向高層所提供的功能性的支持，高層利用低層的“服務(wù)”來開展工作；某一層的SAP就是上一層可以訪問本層、可以得到服務(wù)的地方。

接口

接口就是相鄰層之間進行信息交換必須遵守的規(guī)則。服務(wù)定義了兩層之間的接口。

第7頁,共55頁，2024年2月25日，星期天8.1.2業(yè)務(wù)原語請求原語（REQUEST）

用戶請求一種功能的原語。指示原語（INDICATION）

業(yè)務(wù)提供者請求一種功能或指示一種功能已經(jīng)完成的原語。響應(yīng)原語（RESPONSE）

用戶表示已經(jīng)完成由指示原語請求功能的原語。證實原語（CONFIRM）

業(yè)務(wù)提供者表示已完成由請求原語要求的功能的原語。第8頁,共55頁，2024年2月25日，星期天SAPSAP①請求④證實③響應(yīng)②指示用戶A用戶B圖8.2通信原語的使用第9頁,共55頁，2024年2月25日，星期天8.1.3數(shù)據(jù)單元接口數(shù)據(jù)單元（IDU）

層間傳送的數(shù)據(jù)塊整體，包括用戶和業(yè)務(wù)提供者在業(yè)務(wù)接入點相互傳送的數(shù)據(jù)。數(shù)據(jù)一部分來自對等實體，一部分來自相鄰層。接口控制信息（ICI）

僅在相鄰層間傳送數(shù)據(jù)，用于層間互控。ICI是IDU的一個組成部分。業(yè)務(wù)數(shù)據(jù)單元（SDU）

高層的對等通信實體之間傳送的數(shù)據(jù)定義為本層的SDU。第10頁,共55頁，2024年2月25日，星期天規(guī)程控制信息（PCI）

本層實體和對等層實體間傳送的為完成本層通信規(guī)程而產(chǎn)生的信息。規(guī)程數(shù)據(jù)單元（PDU）

本層的SDU和本層的PCI兩者的組合叫本層的PDU，可寫成PDU=PCI+SDU。第11頁,共55頁，2024年2月25日，星期天ICISDUPDUPCIICIIDUIDUN+1層N層N-1層圖8.3傳送數(shù)據(jù)單元關(guān)系（a）上層向下層傳送數(shù)據(jù)第12頁,共55頁，2024年2月25日，星期天ICISDUPDUPCIICIIDUIDUN+1層N層N-1層圖8.3傳送數(shù)據(jù)單元關(guān)系（b）下層向上層傳送數(shù)據(jù)第13頁,共55頁，2024年2月25日，星期天第14頁,共55頁，2024年2月25日，星期天8.1.4開放系統(tǒng)互聯(lián)參考模型應(yīng)用層表示層會晤層傳輸層網(wǎng)絡(luò)層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層應(yīng)用層表示層會晤層傳輸層網(wǎng)絡(luò)層鏈路層物理層圖8.4OSI參考模型第15頁,共55頁，2024年2月25日，星期天物理層

提供用于建立、保持和斷開物理連接的過程條件。包括規(guī)定機械的、電氣的規(guī)程和功能屬性。鏈路層

負責(zé)建立、維持和釋放鏈路連接，實現(xiàn)無差錯傳輸?shù)墓δ?。網(wǎng)絡(luò)層

也稱通信子層,提供SDU路由選擇和交換功能，控制通信子網(wǎng)的工作，并關(guān)心擁塞控制、計費及異種網(wǎng)絡(luò)的互聯(lián)問題。第16頁,共55頁，2024年2月25日，星期天運輸層

實現(xiàn)端到端的連接控制，為端到端間提供透明的傳送通道。會晤層

會晤層關(guān)心會話連接的特征。其主要功能是在建立會晤時，核實對方身份，確定何方支付費用，選擇一致的通信方式等。表示層

主要功能是以一種收發(fā)雙方的規(guī)程和設(shè)置都明白的方式提供一種數(shù)據(jù)傳送機制。應(yīng)用層

其主要任務(wù)是為用戶提供直接的服務(wù)。第17頁,共55頁，2024年2月25日，星期天8.1.5互聯(lián)TCP/IP參考模型7應(yīng)用層6表示層5會話層4傳輸層3網(wǎng)絡(luò)層2鏈路層1物理層4應(yīng)用層3運輸層2互聯(lián)網(wǎng)絡(luò)層1通信子網(wǎng)層OSITCP/IP圖8.5TCP/IP參考模型第18頁,共55頁，2024年2月25日，星期天互聯(lián)網(wǎng)絡(luò)體系結(jié)構(gòu)分為四層互聯(lián)網(wǎng)層采用了IP協(xié)議傳輸層定義了TCP、UDP、ICMP等協(xié)議物理層+鏈路層組成通信子網(wǎng)層，是主機與局域網(wǎng)的接口第19頁,共55頁，2024年2月25日，星期天8.1.6標準化組織ITU國際電信聯(lián)盟ANSI美國國家標準化協(xié)會ETSI歐洲電信標準化協(xié)會IETFInternet工程特別工作組IRTFInternet研究工作組ATM論壇等第20頁,共55頁，2024年2月25日，星期天8.2排隊論基礎(chǔ)8.2.1排隊論基本概念8.2.2M/M/1排隊模型8.2.3排隊論中Little定理第21頁,共55頁，2024年2月25日，星期天排隊論是通信的業(yè)務(wù)分析和性能計算的理論基礎(chǔ)。資源的有限性和需求的隨機性是排隊現(xiàn)象的基礎(chǔ)。要求服務(wù)的顧客和提供服務(wù)的服務(wù)員雙方構(gòu)成的系統(tǒng)通常稱為排隊系統(tǒng)。通信網(wǎng)中信息流和信道，傳送的數(shù)據(jù)和中央處理單元，都是“顧客”和“服務(wù)員”關(guān)系。第22頁,共55頁，2024年2月25日，星期天8.2.1排隊論基本概念排隊系統(tǒng)的三要素

為窗口數(shù)或服務(wù)員數(shù)

第23頁,共55頁，2024年2月25日，星期天顧客到達率一般排隊系統(tǒng)中顧客到達是隨機的，系統(tǒng)內(nèi)顧客數(shù)是一個隨機量。顧客到達的密度和以什么樣的規(guī)律到達，對系統(tǒng)的影響很大。前后兩個顧客到達的時間間隔是個隨機量。的計算平均值為平均到達間隔時間，其倒數(shù)為平均到達率，即：平均到達率是排隊系統(tǒng)重要參數(shù)，表示平均每秒內(nèi)到達的顧客數(shù)。越小，系統(tǒng)負載越輕。第24頁,共55頁，2024年2月25日，星期天系統(tǒng)服務(wù)率為表示服務(wù)率的參考量。服務(wù)時間也是隨機變量，其統(tǒng)計平均值稱為平均服務(wù)時間，的倒數(shù)是系統(tǒng)服務(wù)率，有表示一個顧客平均占用服務(wù)設(shè)施的時間，為平均每秒內(nèi)顧客被服務(wù)完畢后離去的數(shù)目。第25頁,共55頁，2024年2月25日，星期天上式表明信息流量密度必須滿足，其物理意義是單位時間內(nèi)平均達到的顧客數(shù)目必須小于系統(tǒng)容量，否則系統(tǒng)中排隊的顧客數(shù)目會無限制地增加。實際上排隊系統(tǒng)的容量總是有限的。將導(dǎo)致系統(tǒng)溢出而失去某些顧客。定義：信息流量密度第26頁,共55頁，2024年2月25日，星期天可以求出排隊系統(tǒng)的三個特性參數(shù)：（1）平均系統(tǒng)隊列長度E（n）（2）平均停留時間T：假定有一個顧客到達排隊系統(tǒng)，經(jīng)過排隊等待、服務(wù)好正要離開時，有N個顧客在排隊，這正是該顧客平均等待期間T內(nèi)到達的顧客平均數(shù)，等于T乘以平均到達率，而于是，（3）排隊等待時間W等于T減去平均服務(wù)時間（即平均服務(wù)率的倒數(shù)）第27頁,共55頁，2024年2月25日，星期天分組分組信道分組到達率λ終端圖8.8分組在終端中排隊和轉(zhuǎn)發(fā)第28頁,共55頁，2024年2月25日，星期天8.2.3排隊論中Little定理Little定理 系統(tǒng)中的平均顧客數(shù)E(n)等于顧客平均等待時間E(T)乘以顧客平均到達率λ。 即： E(n)=E(T)λ第29頁,共55頁，2024年2月25日，星期天8.3通信網(wǎng)絡(luò)拓撲結(jié)構(gòu)8.3.1圖論基本概念8.3.2圖的矩陣表示第30頁,共55頁，2024年2月25日，星期天8.3.1圖論基本概念圖（見圖8.10）

鏈 圖中沒有重復(fù)的邊序列，在鏈中每條邊只能出現(xiàn)一次。徑 徑是一個圖中既無重復(fù)邊，又無重復(fù)節(jié)點的邊序列。環(huán) 環(huán)是起點與終點為同一節(jié)點的鏈，即閉鏈。樹 樹有n個端，n-1條邊的聯(lián)結(jié)圖（圖內(nèi)任何兩個端之間至少有一條徑）。生成樹是覆蓋聯(lián)結(jié)圖所有端的樹。第31頁,共55頁，2024年2月25日，星期天v1v2v3v1v2v3v1v2v3（a）（b）（c）圖8.10各種圖的幾何表示e1e3e4e2e2e1e4e3第32頁,共55頁，2024年2月25日，星期天(e1,e3,e5,e4,e2)為鏈(e1,e3,e5)為徑v1v5v4v3v2e1e4e3e2e5e6圖8.11圖的鏈、徑、環(huán)第33頁,共55頁，2024年2月25日，星期天8.3.2圖的矩陣表示圖可與矩陣一一對應(yīng)。鄰接陣 鄰接陣表示圖中節(jié)點與節(jié)點之間的關(guān)系。即：C=[cij]n*n

cij=1若vi到vj有邊0若vi到vj無邊第34頁,共55頁，2024年2月25日，星期天v1v5v4v3v2e1e4e3e2e5e6圖8.12圖的矩陣表示e7第35頁,共55頁，2024年2月25日，星期天C陣的冪其中，式中各項可以是0或1，要使，必有，即到有邊，到也有邊。因而到有一條長為2的徑。徑長表示這條徑中的邊數(shù)。由此可知：若則就是到的徑長為m的徑數(shù)。第36頁,共55頁，2024年2月25日，星期天8.4最短徑8.4.1無約束條件最小生成樹（Prim法）8.4.2節(jié)點間最短徑8.4.3所有節(jié)點間最短路徑算法第37頁,共55頁，2024年2月25日，星期天8.4.1無約束條件最小生成樹一個聯(lián)結(jié)圖G如果本身不是一棵樹，在滿足一定條件下至少存在一棵樹是最小生成樹。尋找最小生成樹是一個常見的優(yōu)化問題。已知聯(lián)結(jié)圖G有n個節(jié)點，節(jié)點間距離為，如果和間無連接，。求最小生成樹的問題即是求n-1條邊的權(quán)的和最小的聯(lián)結(jié)子圖問題?？煞譃閮煞N情況：一種是無約束條件的情況，另一種是有約束條件情況。求無約束條件最短主樹的算法:（1）順序取節(jié)點的普列（Prim）算法，簡稱P算法；（2）順序取邊的克魯斯格爾（Kruskal）算法，簡稱K算法。第38頁,共55頁，2024年2月25日，星期天普列算法（P算法）步驟

第39頁,共55頁，2024年2月25日，星期天例8.1v1v2v3v4v55242310圖8.13最短主樹的算法14第40頁,共55頁，2024年2月25日，星期天樹枝總長為v1v2v3v4v5223圖8.14最短主樹1第41頁,共55頁，2024年2月25日，星期天P算法從開始到終止共n-1步，每步須對個中的節(jié)點與個中的節(jié)點間的距離進行比較，求出最小者?？梢姷诓街幸龃伪容^，由此可得出P算法計算量為：這是的數(shù)量級。第42頁,共55頁，2024年2月25日，星期天8.4.2節(jié)點間最短徑當通信拓撲結(jié)構(gòu)已被確定，尋找站間最短徑問題有兩種情況，求指定節(jié)點到其他節(jié)點的最短徑及求任意兩節(jié)點間最短徑。指定節(jié)點至其他端最短徑算法：給定圖G，已知所有邊的權(quán)，指定節(jié)點至其他節(jié)點的最短徑可用迪克斯恰算法（E.Dijkstra），簡稱D算法。D算法把節(jié)點集分為兩組，一組稱為置定點集，另一組稱為未置定點集，每點逐步賦予標定值。對于未置定點，所賦的值是暫時的，隨算法進展而調(diào)整。第43頁,共55頁，2024年2月25日，星期天迪克斯恰算法（D算法）第44頁,共55頁，2024年2月25日，星期天例8.2用D算法計算最短徑和它徑長vsv5v4v3v61.515.64.00.55.01.2圖8.15最短徑長的計算6.73.12.0v19.2v2第45頁,共55頁，2024年2月25日，星期天VsV1V2V3V4V5V6置定值最短徑長0∞0.5∞2222∞1.51.5∞∞1.71.7∞∞9.79.78.48.48.4∞∞∞5.55.55.1VsV1V3V4V2V6V5ws=0w1=0.5w3=1.5w4=1.7w2=2w6=5.1w5=8.4第46頁,共55頁，2024年2月25日，星期天若要找出各最短徑的路由，可查表中暫置值變更情況。從第二行起都沒有變更，所以都是從來的邊，即。這一列在后變更一次，則路由是。這一列值在和后均變更，路由是