【文章內(nèi)容簡介】 議（生成樹協(xié)議），以網(wǎng)絡(luò)中一臺交換機為節(jié)點生成一棵轉(zhuǎn)發(fā)樹，而樹是沒有環(huán)路的，這樣所有的數(shù)據(jù)都只在這棵 樹所指示的路徑上傳輸，就不會產(chǎn)生廣播風(fēng)暴 。） 廣播風(fēng)暴（ broadcast storm）簡單的講是指當(dāng)廣播數(shù)據(jù)充斥網(wǎng)絡(luò)無法處理，并占用大量 網(wǎng)絡(luò)帶寬 ，導(dǎo)致正常業(yè)務(wù)不能運行，甚至徹底癱瘓，這就發(fā)生了 “廣播風(fēng)暴 ”。一個 數(shù)據(jù)幀 或包被傳輸?shù)奖镜?網(wǎng)段 （由 廣播域 定義）上的每個 節(jié)點 就是廣播；由于網(wǎng)絡(luò)拓?fù)?的設(shè)計和連接問題，或其他原因?qū)е聫V播在網(wǎng)段內(nèi)大 量復(fù)制，傳播 數(shù)據(jù)幀 ，導(dǎo)致網(wǎng)絡(luò)性能下降，甚至 網(wǎng)絡(luò)癱瘓 ，這就是廣播風(fēng)暴。 ） 過程 ： （ 1）選擇根網(wǎng)橋： 在 全網(wǎng)中選擇一個根網(wǎng)橋 ： BID 最小的 被選舉為根網(wǎng)橋。 （ 2）選擇根端口： 在每個非根交換機上選擇根端口 ： 路徑成本 最 低的端口 為 根端口 ； 路徑成本相同 ， BID 較小 的優(yōu)先極高 ， 稱為根端口。 （ 3）選擇指定端口： 在每條鏈路上選擇一個指定端口，根網(wǎng)橋上所有端口都是指定端口 。 （ 1） STP 的基本原理是，通過在 交換機 之間傳遞一種特殊的協(xié)議 報文 ， 網(wǎng)橋協(xié)議數(shù)據(jù)單元 （ Bridge Protocol Data Unit，簡稱 BPDU），來確定網(wǎng)絡(luò)的 拓?fù)浣Y(jié)構(gòu) 。 BPDU 有兩種，配置 BPDU（ Configuration BPDU）和 TCN BPDU。前者是用于計算無環(huán)的 生成樹 的，后者則是用于在二層網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時產(chǎn)生用來縮短 MAC 表項的刷新時間的（由默認(rèn)的 300s 縮短為 15s）。該協(xié)議的原理是按照樹的結(jié)構(gòu)來構(gòu)造網(wǎng)絡(luò)拓?fù)洌W(wǎng)絡(luò)中的環(huán)路，避免由于環(huán)路的存在而造成 廣播風(fēng)暴 問題。 （ 2） STP 的基本思想 就是按照 樹 的結(jié)構(gòu)構(gòu)造網(wǎng)絡(luò)的 拓?fù)浣Y(jié)構(gòu) ，樹的根是一個稱為根橋的橋設(shè)備，根橋的確立是由 交換機 或網(wǎng)橋的 BID（ Bridge ID）確定的， BID 最小的設(shè)備成為二層 網(wǎng)絡(luò)中的根橋。由根橋開始，逐級形成一棵樹，根橋定時發(fā)送配置 BPDU，非根橋接收配置 BPDU，刷新最佳 BPDU 并轉(zhuǎn)發(fā)。這里的最佳 BPDU 指的是當(dāng)前根橋所發(fā)送的 BPDU。如果接收到了下級 BPDU（新接入的設(shè)備會發(fā)送 BPDU，但該設(shè)備的 BID 比當(dāng)前根橋大），接收到該下級 BPDU 的設(shè)備將會向新接入的設(shè)備發(fā)送自己存儲的最佳 BPDU，以告知其當(dāng)前網(wǎng)絡(luò)中根橋；如果接收到的 BPDU更優(yōu)，將會重新計算 生成樹 拓?fù)?。?dāng)非根橋在離上一次接收到最佳 BPDU 最長壽命（ Max Age，默認(rèn) 20s）后還沒有接收到最佳 BPDU的時候，該端口將進入監(jiān)聽狀態(tài)，該設(shè)備將產(chǎn)生 TCN BPDU，并從根端口轉(zhuǎn)發(fā)出去，從指定端口接收到 TCN BPDU 的上級設(shè)備將發(fā)送確認(rèn)，然后再向上級設(shè)備發(fā)送 TCN BPDU，此過程持續(xù)到根橋為止，然后根橋在其后發(fā)送的配置 BPDU 中將攜帶標(biāo)記表明拓?fù)湟寻l(fā)生變化，網(wǎng)絡(luò)中的所有設(shè)備接收到后將 CAM 表項的刷新時間從 300s 縮短為 15s。整個收斂的時間為 50s 左右。 （ 3） 生成樹協(xié)議 最主要的應(yīng)用是為了避免局域網(wǎng)中的單點故障、網(wǎng)絡(luò)回環(huán)，解決成環(huán) 以太網(wǎng) 網(wǎng)絡(luò)的 “廣播風(fēng)暴 ”問題，從某種意義上說是一種網(wǎng)絡(luò)保護技術(shù)，可以消除由于失誤或者意外帶來的循環(huán)連接。 2 CSPF： 約束 最短路徑優(yōu)先 （ ConstrainedShortest Path First） CSPF 是一種改進的最短路徑優(yōu)先算法，在計算通過網(wǎng)絡(luò)的最短路徑時，將特定的約束（ 鏈路 ，代價， 下一跳 ，可用帶寬 ）也考慮進去。CSPF 基于資源的可用性和所選部分是否違反用戶策略約束，在當(dāng)前拓?fù)浣Y(jié)構(gòu)中刪除不滿足條件的節(jié)點和鏈路，然后再通過 SPF 算法計算出一條滿足約束條件的最短路徑，包括一組 LSR（ Link State Request）地址。路徑計算的具體過程為：（ 1）對比 TEDB中的每一個鏈路，裁減不滿足帶寬和顏色等要求的鏈路；（ 2）在剪切以后的拓?fù)渲胁捎米疃搪窂剿惴ǎ?SPF 算法），得到一條滿足 LSP 的約束條件的最短路徑；（ 3）如果仍有多條路徑，選擇跳數(shù)最少的路徑；（ 4）如果仍有多條路徑，根據(jù)配置的負(fù)載分擔(dān)策略進行選擇 。 流量工程： 繞過 網(wǎng)絡(luò)中已知的瓶頸和阻塞點 ， 將 業(yè)務(wù) 映射到現(xiàn)有拓?fù)渖系臉I(yè)務(wù) ，將成為 ISP（ Inter service provider） 一個非常重要的 工具； ISP 必須配置一個能夠使他們的客戶連接到他們網(wǎng)絡(luò)上的物理拓?fù)浣Y(jié)構(gòu)。在網(wǎng)絡(luò)部署完畢后， ISP 必須將客戶的業(yè)務(wù)流映射到網(wǎng)絡(luò)的物理拓?fù)渖稀?LSR通過 對 TED 中 的信息使用 CSPF算法決定 每條 LSP 的 物理路徑 。 2 MMPP： 馬氏 調(diào)制泊松過程 （ Markov modulated Poisson process） 是一個泊松過程，其瞬間泊松到達(dá)率是一個平穩(wěn)的隨機過程，且受到另一個泊松過程的調(diào)制，另一個泊松過程的發(fā)生與否取決于一個不可觀測的隱馬爾科夫過程所處的狀態(tài)。一般有 n 個狀態(tài)，任意 i 個狀態(tài)是一個狀態(tài)依賴速率參數(shù)為 i? 的泊松過程，狀態(tài)之間的轉(zhuǎn)移為一個基本的連續(xù)時間的馬爾科夫鏈所控制。 排隊論 (Queuing Theory)： 是研究系統(tǒng)隨機聚散現(xiàn)象和隨機服務(wù)系統(tǒng)工作過程的數(shù)學(xué)理論和方法，又稱隨機服務(wù)系統(tǒng)理論，為 運籌學(xué) 的一個分支。 2 語義透明 ： ?ATM 的語義透明性是指信息經(jīng)過 ATM 網(wǎng)絡(luò)后沒有誤碼也沒有信元的丟失。語義透明性要求：從源到目的地傳送信息時只能有很少的誤碼。誤碼通常有兩種，一是由于信元的丟失而造成一個信元內(nèi)的所有比特丟失，另一種是由于系統(tǒng)本身的原因和環(huán)境原因造成的單個比特的錯誤和突發(fā)錯誤。 語義透明是業(yè)務(wù)傳送的需求，要求 來自用戶的 信息在通信過程中，信息內(nèi)容不被改變，信息交互雙方或多方之間，不因交互手段改變各自的意思。 在實際通信中，為了實現(xiàn)語義透明，需要采用很多措施，對于誤碼、丟失、誤插，需要采用流量控制及差錯控制解決，對于編碼問題，采用轉(zhuǎn)義 控制來解決，在語義透明中，信息量是核心問題。 時間透明 ： 也是業(yè)務(wù)傳送的需求， 定義為沒有 時延及 時延抖動 。要求 交互雙方 ， 在可接受的時間范圍內(nèi)，收到對方的信息與本地或面對面交流一樣，即可以被無延遲地送到，強調(diào)通信的實時性。 對通信過程的控制， 產(chǎn)生技術(shù)性約束， 糾錯和嵌入式技術(shù)，是核心問題。 2 單純形法 ：求解線性規(guī)劃問題的通用方法。 它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n 維向量空間 Rn 中的多面 凸集 ，其最優(yōu) 值如果存在 ， 必在該凸集的某頂點處達(dá)到。頂點所對應(yīng)的 可行解 稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進行。因基本可行解的個數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題 的最優(yōu)解 。如果問題無最優(yōu)解也可用此法判別。 （ 2） 根據(jù)單純形法的原理，在 線性規(guī)劃 問題中， 決策變量 （控制變量） x1， x2， …x n 的值稱為一個解 ,滿足所有的 約束條件 的解稱為 可行解 。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為 最優(yōu)解 。這樣，一個或多個最優(yōu)解能在整個由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。 （ 3）單純形法的一般解題步驟可 歸納如下：①把線性規(guī)劃問題的約束方程組 表達(dá)成典范型方程組，找出基本 可行解 作為初始基可行解。 ② 若基本可行解不存在，即約束條件有矛盾，則問題無解。 ③ 若基本可行 解存在，從初始基本可行解作為起點，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。 ④ 按步驟 3 進行迭代 ,直到對應(yīng)檢驗數(shù)滿足最優(yōu)性條件（這時目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。 ⑤ 若迭代過程中發(fā)現(xiàn)問題的目標(biāo) 函數(shù)值 無界，則終止 迭代 。 網(wǎng)絡(luò)單純形法 ： （后面） 找最小生成樹構(gòu)成環(huán)的邊，從環(huán)里面增加一條新邊，減掉一條舊邊，就構(gòu)成了樹的變化，對應(yīng)于單純形法中凸點之間的轉(zhuǎn)換。找到一條合適的新邊加入原有生成樹，以便于這條生成樹的成本降低。同時從原來的環(huán)里去除一條舊邊，才能構(gòu)造一棵新的生成樹，因為樹是不允許有環(huán)的。思路：（ 1）以一個初始生成樹為起點（該生成樹包含網(wǎng)絡(luò)的所有節(jié)點）；（ 2）可行樹解 x 與生成樹 T 相關(guān)聯(lián)，且 0?ijx if ij 不是生成樹 T 的邊；（ 3）通過查找所有可行樹解，得最優(yōu)解。因為，加入樹外的邊，必然增大成本。 2 易損期 ：易損期是吞吐性能求解的一個參數(shù)， 如果在一段時間區(qū)間有一個用戶占用資源，則此用戶可有效利用資源；若有兩個或以上用戶占用資源則發(fā)生沖突。會發(fā)生沖突的時間區(qū)間稱為易損期。如果易損期能夠求得，那么就能求出沖突概率，可以求得沖突時間和不沖突時間。這樣網(wǎng)絡(luò)的吞吐性能就能求解出來。所以易損期是在網(wǎng)絡(luò)分析過程中至關(guān)重要的一個概念。如果在 tT 到 t 時間內(nèi)，其他用戶產(chǎn)生了數(shù)據(jù)分組，則該分組就會和 t 時刻發(fā)送的分組的頭部發(fā)生碰撞；同樣，在 t 和 t+T 之間產(chǎn)生的任何分組都將和 t 時刻發(fā)送的分組的尾部發(fā)生碰撞。時間區(qū)間 [tT,t+T]稱為易損期。（這里， t:分組開始發(fā)送時間， T：分組發(fā)送時長）。 ：剩余服務(wù)時間 是 在 M/G/1 求解問題中常用到的一個參數(shù)， 正在接受的服務(wù)還有多少時間服務(wù)結(jié)束。關(guān)心的是隨時間變化的統(tǒng)計平均值。（剩余服務(wù)時間在 M/G/1 求解問題中常用到的一個參數(shù)，在 M/G/1 模型中，用戶到達(dá)人數(shù)服從泊松分布，服務(wù)時間相同且為任意分布，只有一個服務(wù)員，在這種情況下，第 i 個顧客等待服務(wù)的時間可以表示為 RSNqWi ?? * ，這里的 Nq表示在第 i 個顧客之前等待的顧客數(shù)目， S 表示平均的服務(wù)時間， R 表示服務(wù)員的剩余服務(wù)時間。如果服務(wù)員處于空閑狀態(tài)，那么 R=0，否則表示某一個顧客接受服務(wù)的剩余服務(wù)時間。）“ M/M/m”是排隊系統(tǒng)的通用表示法。第一個字母表示到達(dá)過程的特征 ， M 表示是無記憶的 Poisson 過程。第二個字母表示服務(wù)時間的概率分布， M 表示指數(shù)分布， G 表示一般分布， D 表示確定性分布。第三個字母表示服務(wù)員的個數(shù)。有時還有第四個字母，表示系統(tǒng)容量的大小。如果沒有第四個字母，則表示系統(tǒng)的容量是無限大的。 基本方法 面向連接服務(wù) ：所謂連接，就是兩個對等實體為進行數(shù)據(jù)通信而進行的一種結(jié)合。面向連接服務(wù)具有連接建立、數(shù)據(jù)傳輸和連接釋放這三個階段。面向連接服務(wù)是在數(shù)據(jù)交換之前，必須先建立連接。當(dāng)數(shù)據(jù)交換結(jié)束后，則必須終止這個連接。在傳送數(shù)據(jù)時是按時序傳送的。面向連接服務(wù)比較適合于在一定期間內(nèi)要向同一目的地發(fā)送許多報文的情況。對于發(fā)送很短的零星報文，面向連接服務(wù)的開銷就顯得過大了。 無連接服務(wù) ：在無連接服務(wù)的情況下，兩個實體之間的通信不需要先建立好一個連接，因此其下層的有關(guān)資源不需要事先進行預(yù)定保留。這些資源將在數(shù)據(jù)傳輸時動態(tài)地進行分配。無連接服務(wù)的另一特征就是它不需要通信的兩個實體同時是活躍的，當(dāng)發(fā)送端的實體正在進行發(fā)送時，它才必須是活躍 的。這時接收端的實體并不一定必須是活躍的。只有當(dāng)接收端的實體正在進行接收時，它才必須是活躍的。無連接服務(wù)的優(yōu)點是靈活方便和比較迅速。但無連接服務(wù)不能防止報文的丟失、重復(fù)或失序。無連接服務(wù)的特點不需要接收端做任何響應(yīng)，因而是一種不可靠的服務(wù)。這種服務(wù)常被描述為“盡最大努力交付”或“盡力而為”。 （與所涉及到的時間透明性有關(guān)，如果時間透明性要求比較高的話，不能采用面向連接的服務(wù)，無連接的時間透明性好，面向連接的時間透明性差，通信服務(wù)包括兩大類一個是對時間敏感一個是對時間不敏感，通常對時間敏感采用無連接服務(wù)。） 、 前向糾錯的計算方法 ： 為了提高時間透明性，用戶應(yīng)盡可能降低傳輸錯誤。所以在通信里面通常采用前向糾錯做法，以便減少接收出錯的情況。 前向糾錯也叫前向 糾錯碼 (Forward Error Correction 簡稱 FEC)，是增加 數(shù)據(jù)通訊 可信度的方法。在單向通訊信道中，一旦錯誤被發(fā)現(xiàn)，其接收器將無權(quán)再請求傳輸。 FEC 是利用數(shù)據(jù)進行傳輸冗長信息的方法，當(dāng)傳輸中出現(xiàn)錯誤，將允許接收器再建數(shù)據(jù)。 常用的檢錯方法有兩類：一類是奇偶校驗，另一類是 循環(huán)冗余校驗碼 （ Cyclic Redundancy Check）。其基本思路是發(fā)端按照給定的規(guī)則在 K 個信息比特后面增加 L 個按照某種規(guī)則計算的校驗比特，在接收端對收到的信息比特重新計算 L 個校驗比特。比較接收到的校驗比特和本地重新計算的校驗比特，如果相同則認(rèn)為傳輸無誤，否則認(rèn)為傳輸有錯。 ?奇偶校驗碼是 一種增加二進制傳輸系統(tǒng)最小距離的簡單和廣泛采用的方法。是一種通過增加 冗余位 使得碼字中 1的個數(shù)恒為奇數(shù)或偶數(shù)的編碼方法，它是一種檢錯碼。在實際使用時又可分為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗等幾種。 奇偶校驗可描述為：給每一個碼字加一個校驗位，用它來構(gòu)成奇性或偶性校驗。可以看出，附加碼元 d2，是簡單地用來使每個字成為偶性的。因此，若有一個碼元是錯的，就可以分辨得出，因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編碼中 1 個個數(shù)為奇數(shù)（奇校驗）或者為偶數(shù)（偶校驗），從而使碼距變?yōu)?2。因為其利用的是編碼中 1 的個數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯誤。 ?CRC 的基本原理是： 在 K 位信息碼后再拼接 R 位的校驗碼，整個編碼長度為 N 位，因此，這種編碼也叫（ N， K）碼。對于一個給定的（ N， K）碼，可以證明存在一個 最高次冪 為 NK=R 的多項式 G(x)。根據(jù) G(x)可以生成 K 位信息的校驗碼，而 G(x)叫做這個 CRC 碼的生成多項式。 校驗碼的具體生成過程為：假設(shè)要發(fā)送的