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

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

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

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

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

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

協(xié)議(Protocol)

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

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

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

接口

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

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

用戶請(qǐng)求一種功能的原語(yǔ)。指示原語(yǔ)（INDICATION）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第39頁(yè),共55頁(yè)，2024年2月25日，星期天例8.1v1v2v3v4v55242310圖8.13最短主樹(shù)的算法14第40頁(yè),共55頁(yè)，2024年2月25日，星期天樹(shù)枝總長(zhǎng)為v1v2v3v4v5223圖8.14最短主樹(shù)1第41頁(yè),共55頁(yè)，2024年2月25日，星期天P算法從開(kāi)始到終止共n-1步，每步須對(duì)個(gè)中的節(jié)點(diǎn)與個(gè)中的節(jié)點(diǎn)間的距離進(jìn)行比較，求出最小者?？梢?jiàn)第步中要做次比較，由此可得出P算法計(jì)算量為：這是的數(shù)量級(jí)。第42頁(yè),共55頁(yè)，2024年2月25日，星期天8.4.2節(jié)點(diǎn)間最短徑當(dāng)通信拓?fù)浣Y(jié)構(gòu)已被確定，尋找站間最短徑問(wèn)題有兩種情況，求指定節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短徑及求任意兩節(jié)點(diǎn)間最短徑。指定節(jié)點(diǎn)至其他端最短徑算法：給定圖G，已知所有邊的權(quán)，指定節(jié)點(diǎn)至其他節(jié)點(diǎn)的最短徑可用迪克斯恰算法（E.Dijkstra），簡(jiǎn)稱D算法。D算法把節(jié)點(diǎn)集分為兩組，一組稱為置定點(diǎn)集，另一組稱為未置定點(diǎn)集，每點(diǎn)逐步賦予標(biāo)定值。對(duì)于未置定點(diǎn)，所賦的值是暫時(shí)的，隨算法進(jìn)展而調(diào)整。第43頁(yè),共55頁(yè)，2024年2月25日，星期天迪克斯恰算法（D算法）第44頁(yè),共55頁(yè)，2024年2月25日，星期天例8.2用D算法計(jì)算最短徑和它徑長(zhǎng)vsv5v4v3v61.515.64.00.55.01.2圖8.15最短徑長(zhǎng)的計(jì)算6.73.12.0v19.2v2第45頁(yè),共55頁(yè)，2024年2月25日，星期天VsV1V2V3V4V5V6置定值最短徑長(zhǎng)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頁(yè),共55頁(yè)，2024年2月25日，星期天若要找出各最短徑的路由，可查表中暫置值變更情況。從第二行起都沒(méi)有變更，所以都是從來(lái)的邊，即。這一列在后變更一次，則路由是。這一列值在和后均變更，路由是