【正文】 制 ： 發(fā)送方和接收發(fā)都維持一個(gè)窗口，窗口內(nèi)部包含哪些可以接收的序列號(hào)。 校驗(yàn)碼的具體生成過(guò)程為：假設(shè)要發(fā)送的信息用多項(xiàng)式 C(X)表示，將 C(x)左移 R 位（可表示成 C(x)*xR），這樣 C(x)的右邊就會(huì)空出 R 位，這就是校驗(yàn)碼的位置。對(duì)于一個(gè)給定的（ N， K）碼，可以證明存在一個(gè) 最高次冪 為 NK=R 的多項(xiàng)式 G(x)。因?yàn)槠淅玫氖蔷幋a中 1 的個(gè)數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。因此，若有一個(gè)碼元是錯(cuò)的，就可以分辨得出，因?yàn)槠媾夹ｒ?yàn)將成為奇性。 奇偶校驗(yàn)可描述為：給每一個(gè)碼字加一個(gè)校驗(yàn)位，用它來(lái)構(gòu)成奇性或偶性校驗(yàn)。是一種通過(guò)增加 冗余位 使得碼字中 1的個(gè)數(shù)恒為奇數(shù)或偶數(shù)的編碼方法，它是一種檢錯(cuò)碼。比較接收到的校驗(yàn)比特和本地重新計(jì)算的校驗(yàn)比特，如果相同則認(rèn)為傳輸無(wú)誤，否則認(rèn)為傳輸有錯(cuò)。 常用的檢錯(cuò)方法有兩類：一類是奇偶校驗(yàn)，另一類是 循環(huán)冗余校驗(yàn)碼 （ Cyclic Redundancy Check）。在單向通訊信道中，一旦錯(cuò)誤被發(fā)現(xiàn)，其接收器將無(wú)權(quán)再請(qǐng)求傳輸。所以在通信里面通常采用前向糾錯(cuò)做法，以便減少接收出錯(cuò)的情況。 （與所涉及到的時(shí)間透明性有關(guān)，如果時(shí)間透明性要求比較高的話，不能采用面向連接的服務(wù)，無(wú)連接的時(shí)間透明性好，面向連接的時(shí)間透明性差，通信服務(wù)包括兩大類一個(gè)是對(duì)時(shí)間敏感一個(gè)是對(duì)時(shí)間不敏感，通常對(duì)時(shí)間敏感采用無(wú)連接服務(wù)。無(wú)連接服務(wù)的特點(diǎn)不需要接收端做任何響應(yīng)，因而是一種不可靠的服務(wù)。無(wú)連接服務(wù)的優(yōu)點(diǎn)是靈活方便和比較迅速。這時(shí)接收端的實(shí)體并不一定必須是活躍的。這些資源將在數(shù)據(jù)傳輸時(shí)動(dòng)態(tài)地進(jìn)行分配。對(duì)于發(fā)送很短的零星報(bào)文，面向連接服務(wù)的開(kāi)銷就顯得過(guò)大了。在傳送數(shù)據(jù)時(shí)是按時(shí)序傳送的。面向連接服務(wù)是在數(shù)據(jù)交換之前，必須先建立連接。 基本方法 面向連接服務(wù) ：所謂連接，就是兩個(gè)對(duì)等實(shí)體為進(jìn)行數(shù)據(jù)通信而進(jìn)行的一種結(jié)合。有時(shí)還有第四個(gè)字母，表示系統(tǒng)容量的大小。第二個(gè)字母表示服務(wù)時(shí)間的概率分布， M 表示指數(shù)分布， G 表示一般分布， D 表示確定性分布。）“ M/M/m”是排隊(duì)系統(tǒng)的通用表示法。（剩余服務(wù)時(shí)間在 M/G/1 求解問(wèn)題中常用到的一個(gè)參數(shù)，在 M/G/1 模型中，用戶到達(dá)人數(shù)服從泊松分布，服務(wù)時(shí)間相同且為任意分布，只有一個(gè)服務(wù)員，在這種情況下，第 i 個(gè)顧客等待服務(wù)的時(shí)間可以表示為 RSNqWi ?? * ，這里的 Nq表示在第 i 個(gè)顧客之前等待的顧客數(shù)目， S 表示平均的服務(wù)時(shí)間， R 表示服務(wù)員的剩余服務(wù)時(shí)間。 ：剩余服務(wù)時(shí)間 是 在 M/G/1 求解問(wèn)題中常用到的一個(gè)參數(shù)， 正在接受的服務(wù)還有多少時(shí)間服務(wù)結(jié)束。時(shí)間區(qū)間 [tT,t+T]稱為易損期。所以易損期是在網(wǎng)絡(luò)分析過(guò)程中至關(guān)重要的一個(gè)概念。如果易損期能夠求得，那么就能求出沖突概率，可以求得沖突時(shí)間和不沖突時(shí)間。 2 易損期 ：易損期是吞吐性能求解的一個(gè)參數(shù)， 如果在一段時(shí)間區(qū)間有一個(gè)用戶占用資源，則此用戶可有效利用資源；若有兩個(gè)或以上用戶占用資源則發(fā)生沖突。思路：（ 1）以一個(gè)初始生成樹(shù)為起點(diǎn)（該生成樹(shù)包含網(wǎng)絡(luò)的所有節(jié)點(diǎn)）；（ 2）可行樹(shù)解 x 與生成樹(shù) T 相關(guān)聯(lián)，且 0?ijx if ij 不是生成樹(shù) T 的邊；（ 3）通過(guò)查找所有可行樹(shù)解，得最優(yōu)解。找到一條合適的新邊加入原有生成樹(shù)，以便于這條生成樹(shù)的成本降低。 ⑤ 若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo) 函數(shù)值 無(wú)界，則終止 迭代 。 ③ 若基本可行 解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。 （ 3）單純形法的一般解題步驟可 歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組 表達(dá)成典范型方程組，找出基本 可行解 作為初始基可行解。這樣，一個(gè)或多個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。 （ 2） 根據(jù)單純形法的原理，在 線性規(guī)劃 問(wèn)題中， 決策變量 （控制變量） x1， x2， …x n 的值稱為一個(gè)解 ,滿足所有的 約束條件 的解稱為 可行解 。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題 的最優(yōu)解 。頂點(diǎn)所對(duì)應(yīng)的 可行解 稱為基本可行解。 2 單純形法 ：求解線性規(guī)劃問(wèn)題的通用方法。要求 交互雙方 ， 在可接受的時(shí)間范圍內(nèi)，收到對(duì)方的信息與本地或面對(duì)面交流一樣，即可以被無(wú)延遲地送到，強(qiáng)調(diào)通信的實(shí)時(shí)性。 在實(shí)際通信中，為了實(shí)現(xiàn)語(yǔ)義透明，需要采用很多措施，對(duì)于誤碼、丟失、誤插，需要采用流量控制及差錯(cuò)控制解決，對(duì)于編碼問(wèn)題，采用轉(zhuǎn)義 控制來(lái)解決，在語(yǔ)義透明中，信息量是核心問(wèn)題。誤碼通常有兩種，一是由于信元的丟失而造成一個(gè)信元內(nèi)的所有比特丟失，另一種是由于系統(tǒng)本身的原因和環(huán)境原因造成的單個(gè)比特的錯(cuò)誤和突發(fā)錯(cuò)誤。 2 語(yǔ)義透明 ： ?ATM 的語(yǔ)義透明性是指信息經(jīng)過(guò) ATM 網(wǎng)絡(luò)后沒(méi)有誤碼也沒(méi)有信元的丟失。一般有 n 個(gè)狀態(tài)，任意 i 個(gè)狀態(tài)是一個(gè)狀態(tài)依賴速率參數(shù)為 i? 的泊松過(guò)程，狀態(tài)之間的轉(zhuǎn)移為一個(gè)基本的連續(xù)時(shí)間的馬爾科夫鏈所控制。 LSR通過(guò) 對(duì) TED 中 的信息使用 CSPF算法決定 每條 LSP 的 物理路徑 。 流量工程： 繞過(guò) 網(wǎng)絡(luò)中已知的瓶頸和阻塞點(diǎn) ， 將 業(yè)務(wù) 映射到現(xiàn)有拓?fù)渖系臉I(yè)務(wù) ，將成為 ISP（ Inter service provider） 一個(gè)非常重要的 工具； ISP 必須配置一個(gè)能夠使他們的客戶連接到他們網(wǎng)絡(luò)上的物理拓?fù)浣Y(jié)構(gòu)。CSPF 基于資源的可用性和所選部分是否違反用戶策略約束，在當(dāng)前拓?fù)浣Y(jié)構(gòu)中刪除不滿足條件的節(jié)點(diǎn)和鏈路，然后再通過(guò) SPF 算法計(jì)算出一條滿足約束條件的最短路徑，包括一組 LSR（ Link State Request）地址。 （ 3） 生成樹(shù)協(xié)議 最主要的應(yīng)用是為了避免局域網(wǎng)中的單點(diǎn)故障、網(wǎng)絡(luò)回環(huán)，解決成環(huán) 以太網(wǎng) 網(wǎng)絡(luò)的 “廣播風(fēng)暴 ”問(wèn)題，從某種意義上說(shuō)是一種網(wǎng)絡(luò)保護(hù)技術(shù)，可以消除由于失誤或者意外帶來(lái)的循環(huán)連接。當(dāng)非根橋在離上一次接收到最佳 BPDU 最長(zhǎng)壽命（ Max Age，默認(rèn) 20s）后還沒(méi)有接收到最佳 BPDU的時(shí)候，該端口將進(jìn)入監(jiān)聽(tīng)狀態(tài)，該設(shè)備將產(chǎn)生 TCN BPDU，并從根端口轉(zhuǎn)發(fā)出去，從指定端口接收到 TCN BPDU 的上級(jí)設(shè)備將發(fā)送確認(rèn)，然后再向上級(jí)設(shè)備發(fā)送 TCN BPDU，此過(guò)程持續(xù)到根橋?yàn)橹梗缓蟾鶚蛟谄浜蟀l(fā)送的配置 BPDU 中將攜帶標(biāo)記表明拓?fù)湟寻l(fā)生變化，網(wǎng)絡(luò)中的所有設(shè)備接收到后將 CAM 表項(xiàng)的刷新時(shí)間從 300s 縮短為 15s。這里的最佳 BPDU 指的是當(dāng)前根橋所發(fā)送的 BPDU。 （ 2） STP 的基本思想 就是按照 樹(shù) 的結(jié)構(gòu)構(gòu)造網(wǎng)絡(luò)的 拓?fù)浣Y(jié)構(gòu) ，樹(shù)的根是一個(gè)稱為根橋的橋設(shè)備，根橋的確立是由 交換機(jī) 或網(wǎng)橋的 BID（ Bridge ID）確定的， BID 最小的設(shè)備成為二層 網(wǎng)絡(luò)中的根橋。前者是用于計(jì)算無(wú)環(huán)的 生成樹(shù) 的，后者則是用于在二層網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)產(chǎn)生用來(lái)縮短 MAC 表項(xiàng)的刷新時(shí)間的（由默認(rèn)的 300s 縮短為 15s）。 （ 1） STP 的基本原理是，通過(guò)在 交換機(jī) 之間傳遞一種特殊的協(xié)議 報(bào)文 ， 網(wǎng)橋協(xié)議數(shù)據(jù)單元 （ Bridge Protocol Data Unit，簡(jiǎn)稱 BPDU），來(lái)確定網(wǎng)絡(luò)的 拓?fù)浣Y(jié)構(gòu) 。 （ 2）選擇根端口： 在每個(gè)非根交換機(jī)上選擇根端口 ： 路徑成本 最 低的端口 為 根端口 ； 路徑成本相同 ， BID 較小 的優(yōu)先極高 ， 稱為根端口。一個(gè) 數(shù)據(jù)幀 或包被傳輸?shù)奖镜?網(wǎng)段 （由 廣播域 定義）上的每個(gè) 節(jié)點(diǎn) 就是廣播；由于網(wǎng)絡(luò)拓?fù)?的設(shè)計(jì)和連接問(wèn)題，或其他原因?qū)е聫V播在網(wǎng)段內(nèi)大 量復(fù)制，傳播 數(shù)據(jù)幀 ，導(dǎo)致網(wǎng)絡(luò)性能下降，甚至 網(wǎng)絡(luò)癱瘓 ，這就是廣播風(fēng)暴。要消除這種網(wǎng)絡(luò)循環(huán)連接帶來(lái)的網(wǎng)絡(luò)廣播風(fēng)暴可以使用 STP 協(xié)議（生成樹(shù)協(xié)議），以網(wǎng)絡(luò)中一臺(tái)交換機(jī)為節(jié)點(diǎn)生成一棵轉(zhuǎn)發(fā)樹(shù)，而樹(shù)是沒(méi)有環(huán)路的，這樣所有的數(shù)據(jù)都只在這棵 樹(shù)所指示的路徑上傳輸，就不會(huì)產(chǎn)生廣播風(fēng)暴 。 STP 是為了抑制“廣播風(fēng)暴”。 STP： 生成樹(shù)協(xié)議（ Spanning Tree Protocol） ： （局域網(wǎng)、以太網(wǎng)的網(wǎng)橋中使用的生成樹(shù)協(xié)議。 //OSPF 的更新過(guò)程收斂得快是其重要優(yōu)點(diǎn)。（ 3）只有當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)，路由器才向所有路由器用洪泛法發(fā)送此信息。所謂“鏈路狀態(tài)”就是說(shuō)明本路由器都和哪些路由器相鄰，以及該鏈路的“度量”（ metric）。而每一個(gè)相鄰路由器又再將此信息發(fā)往其所有的相鄰路由器（但不再發(fā)送給剛剛發(fā)來(lái)信息的那個(gè)路由器）。和 RIP 協(xié)議相比， OSPF 的三個(gè)要點(diǎn)和 RIP 的都不一樣：（ 1）向本自治系統(tǒng)中所有路由器發(fā)送信息。實(shí)際上，所有的在自治系統(tǒng)內(nèi)部使用的路由選擇協(xié)議（包括 RIP 協(xié)議）都是要尋找一條最短的路徑?！白疃搪窂絻?yōu)先”是因?yàn)槭褂昧?Dijkstra 提出的最短路徑算法 SPF。 “開(kāi)放”表明 OSPF 協(xié)議不是受某一家廠商控制，而是公開(kāi)發(fā)表的。 距離相等路徑的解決方法（ 1） 先到先用；（ 2） 組播更新 周期一半之前的優(yōu)先。 RIP 網(wǎng)絡(luò)有可能產(chǎn)生路由環(huán)路。路由表更新的原則是找出到每個(gè)目的網(wǎng)絡(luò)的最短距離。 RIP 協(xié)議的特點(diǎn)是：（ 1）僅和相鄰路由器交換信息；（ 2）路由器交換的信息是當(dāng)前本路由器所知道的全部信息，即自己的路由表；（ 3）按固定的時(shí)間間隔交換路由信息。 RIP 不能在兩個(gè)網(wǎng)絡(luò)之間同時(shí)使用多條路由。因此，“距離”等于 16 即相當(dāng)于不可達(dá)。 RIP 認(rèn)為好的路由就是它通過(guò)的路由器的數(shù)目少，即“距離短”。“加 1”是因?yàn)榈竭_(dá)目的網(wǎng)絡(luò)后就進(jìn)行直接交付，而到直接連接的網(wǎng)絡(luò)的距離已經(jīng)定義為 1。 RIP 協(xié)議要求網(wǎng)絡(luò)中的每一個(gè)路由器都要維護(hù)從它自己到其他每一個(gè)目的網(wǎng)絡(luò)的距離記錄（因此，這是一組距離，即“距離向量”）。 路由器發(fā)送一個(gè)列表，其中包含他到每一個(gè)目標(biāo)路由器的延時(shí)估計(jì)值；同時(shí)，他也從每一個(gè)鄰居路由器收到一個(gè)類似的列表。（二進(jìn)制堆 ： )lg( VEO ,斐波那契堆(Fibonacci heap): )lg( EVVO ? ） 1 RIP： 路由信息協(xié)議 （ Routing Information Protocol） ：距離矢量路由 是基于距離矢量算法的路由協(xié)議，利用跳數(shù)來(lái)作為計(jì)量標(biāo)準(zhǔn)。（ E10 ？ ）（ 2） prim 算法： ?不斷擴(kuò)展一顆子樹(shù) T=(S,F),F 為 E 子集，知道 S 包括全部頂點(diǎn)，得到最小生成樹(shù) T。 （ 1） kruskal 算法： ?將一條權(quán)最小的邊加入子圖 T中，并保證不形成圈。 把確定樹(shù) T 的問(wèn)題稱為最小生成樹(shù)問(wèn)題。因?yàn)?T 無(wú)回路且連接所有的頂點(diǎn)，所以它必然是一棵樹(shù)，稱為生成樹(shù)，因?yàn)樗吧伞绷藞D G。 1 MST： 最小生成樹(shù) （ Minimum Spanning Tree） ；多播路由算法 對(duì)于一個(gè)無(wú)向連通圖 G=(V,E)，其中 V 是頂點(diǎn)集合， E 是邊的集合，對(duì)于 E 中每一條邊（ u,v），都有一個(gè)權(quán)值 w(u,v)表示連接 u 和 v 的代價(jià)。從算法的觀點(diǎn)，所有因?yàn)檎归_(kāi)節(jié)點(diǎn)而得到的子節(jié)點(diǎn)都會(huì)被加進(jìn)一個(gè)先進(jìn)先出的 隊(duì)列 中。換句話說(shuō)，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。 Dijkstra 單源最短路徑 算法和 Prim 最小生成樹(shù) 算法都采用了和寬度優(yōu)先搜索類似的思想。 深度優(yōu)先搜索所遵循的搜索策略是盡可能 深 地搜索圖。屬于盲目搜索。這一過(guò)程一直進(jìn)行到 已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果將每個(gè)節(jié)點(diǎn)在深度優(yōu)先搜索過(guò)程中的“結(jié)束時(shí)間”排序 (具體做法是創(chuàng)建一個(gè) list,然后在每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)都已被訪問(wèn)的情況下，將該節(jié)點(diǎn)加入 list 結(jié)尾，然后逆轉(zhuǎn)整個(gè)鏈表 ),則我們可以得到所謂的“拓?fù)渑判颉保?topological sort.(搜索原理： 在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的頂點(diǎn)，如果它還有以此為起點(diǎn)而未探測(cè)到的邊，就沿此邊繼續(xù)漢下去。 每次深度優(yōu)先搜索的結(jié)果必然是圖的一個(gè)連通分量。 對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次 。 CAC 方法：本地決策（ 依據(jù)歷史經(jīng)驗(yàn)，設(shè)置固定的允許呼叫的上限 ） ； 基于測(cè)量的決策（ 發(fā)啟方通過(guò)測(cè)量到達(dá)目標(biāo)節(jié)點(diǎn)的丟失率和延時(shí)，決定呼叫的接續(xù)與否 ） ； 基于資源的決策（ 計(jì)算所需與可用的資源，或者執(zhí)行資源預(yù)留操作，再?zèng)Q定呼叫的接續(xù) ） 。 呼叫接納控制已廣泛應(yīng)用于許多通信網(wǎng)中，如 ATM 通信網(wǎng)和移動(dòng)蜂窩系統(tǒng)。相關(guān)文獻(xiàn)提出的呼叫接納控制的標(biāo)準(zhǔn)為：系統(tǒng)預(yù)先估計(jì)新呼叫接納后的用戶 QoS，而當(dāng)所有用戶的 QoS 都達(dá)到要求時(shí)，呼叫才能被接納。其目的是維護(hù)網(wǎng)絡(luò)的穩(wěn)定性、保證無(wú)線鏈路質(zhì)量和合理利用系統(tǒng)容量。（ 5）面向字節(jié)流。（ 4） TCP 提供全雙工通信。在傳送數(shù)據(jù)完畢后，必須釋放已經(jīng)建立的 TCP 連接；（ 2）每一條 TCP 連接只能有兩個(gè)端點(diǎn)，每一條 TCP 連接只能是點(diǎn)對(duì)點(diǎn)的（一對(duì)一）；（ 3）TCP 提供可靠交付的服務(wù)。 TCP 最主要的特點(diǎn)：（ 1） TCP 是面向連接的運(yùn)輸層協(xié)議。 TCP 三次握手的過(guò)程如下： 客戶端發(fā)送 SYN（ SEQ=x）報(bào)文給服務(wù)器端，進(jìn)入 SYN_SEND 狀態(tài)；服務(wù)器端收到 SYN 報(bào)文，回應(yīng)一個(gè) SYN （ SEQ=y） ACK(ACK=x+1）報(bào)文，進(jìn)入 SYN_RECV 狀態(tài)；客戶端收到 服務(wù)器端的 SYN報(bào)文，回應(yīng)一個(gè) ACK(ACK=y+1）報(bào)文，進(jìn)入Established 狀態(tài)。然后接收端實(shí)體對(duì)已成功收到的包發(fā)回一個(gè)相應(yīng)的確認(rèn)（ ACK）；如果發(fā)送端實(shí)體在合理的往返時(shí)延（ RTT）內(nèi)未收到確認(rèn)，那么對(duì)應(yīng)的數(shù)據(jù)包就被假設(shè)為已丟失將會(huì)被進(jìn)行重傳。之后 TCP 把結(jié)果包傳給 IP 層，由它來(lái)通過(guò)網(wǎng)絡(luò)將包傳送給接收端實(shí)體的 TCP 層。 不同主機(jī)的應(yīng)用層之間經(jīng)常需要可靠的、像管道一樣的連接，但是 IP 層不提供這樣的流機(jī)制，而是提供不可靠的包交換。在簡(jiǎn)化的計(jì)算機(jī)網(wǎng)絡(luò) OSI 模型中，它完成