通信網(wǎng)復(fù)習(xí)整理終極版

1、1、 RED(random early detect)，提前隨機(jī)丟棄：擁塞控制是一種主動(dòng)隊(duì)列管理算法。通過(guò)監(jiān)控路由器輸出端口隊(duì)列的平均長(zhǎng)度來(lái)探測(cè)擁塞，一旦平均隊(duì)列長(zhǎng)度超過(guò)一個(gè)閾值，就以一定的概率丟包或者在分組上作標(biāo)記來(lái)通知相應(yīng)的連接來(lái)減小發(fā)送速率，從而緩解網(wǎng)絡(luò)擁塞，也就是說(shuō)在緩沖區(qū)滿之前就按照一定的比例（即丟棄概率）隨機(jī)地將緩沖區(qū)的數(shù)據(jù)丟棄或標(biāo)記。TCP擁塞控制與網(wǎng)絡(luò)層有密切的關(guān)系。網(wǎng)絡(luò)層對(duì)擁塞控制的策略之一就是Drop tail尾部丟棄，緩沖區(qū)溢出時(shí)丟棄。路由器的尾部丟棄往往會(huì)導(dǎo)致一連串分組的丟失，這就使得發(fā)送方出現(xiàn)超時(shí)重傳，使TCP進(jìn)入慢狀態(tài)開(kāi)始，即發(fā)生全局同步現(xiàn)象。為了避免網(wǎng)絡(luò)中全局同步

2、現(xiàn)象，路由器采用RED措施。即使路由器的隊(duì)列維持兩個(gè)參數(shù)，即隊(duì)列長(zhǎng)度最小門(mén)限THmin和最大門(mén)限THmax。每當(dāng)一個(gè)分組到達(dá)時(shí)RED組都先計(jì)算平均隊(duì)列長(zhǎng)度Lav。RED的算法是：（1）若Lav<THmin，則把新到達(dá)的分組放入隊(duì)列進(jìn)行排隊(duì)。（2）若Lav>THmax，則把新到達(dá)的分組丟棄。（3）若THmin<Lav<THmax，則按照某一概率p將新到達(dá)的分組丟棄。RED中的隨機(jī)就體現(xiàn)在（3）中，也就是說(shuō)RED不是等到已經(jīng)發(fā)生網(wǎng)絡(luò)擁塞后才把所有在隊(duì)列尾部的分組全部丟棄，而是在檢測(cè)到網(wǎng)絡(luò)擁塞的早期征兆時(shí)，就先以概率p隨機(jī)丟棄個(gè)別的分組，讓擁塞只在個(gè)別的TCP連接上進(jìn)行，因而

3、避免發(fā)生全局性的擁塞控制。2、GBN ARQ，返回N自動(dòng)請(qǐng)求重發(fā)：差錯(cuò)控制差錯(cuò)控制：自動(dòng)請(qǐng)求重發(fā)；前向糾錯(cuò)控制；混合糾錯(cuò)控制；有四種不同形式的ARQ：停止等待（SW） ARQ、GBN ARQ、選擇重發(fā)（SR） ARQ、并行等待（ARPANET）ARQ。GBN ARQ：運(yùn)用最廣泛。發(fā)信側(cè)不用等待收信側(cè)的應(yīng)答，持續(xù)的發(fā)送多個(gè)幀，假如發(fā)現(xiàn)已發(fā)送的幀中有錯(cuò)誤發(fā)生，那么從那個(gè)發(fā)生錯(cuò)誤的幀開(kāi)始及其之后所有的幀全部再重新發(fā)送，窗口越大重傳幀數(shù)越多。最大窗口值：-1（i通常去3或7）。缺點(diǎn)：一個(gè)分組的差錯(cuò)可能引起大量分組的重傳，這些分組可能已經(jīng)被接收方正確接收了，但由于未按序到達(dá)而被丟棄。SR ARQ：是對(duì)G

4、BN ARQ的改進(jìn)，與GBN ARQ的思路相同，但只重發(fā)出錯(cuò)的幀。這就要求加大接收窗口，以便先收下失序到達(dá)但仍然處在接收窗口中的哪些分組，等到所缺分組收齊后再一并送交上層。同時(shí)要求接收方有對(duì)分組排序的能力，且應(yīng)答應(yīng)包括出錯(cuò)幀N以及那些大于N的已被正確接收的幀的信息。3、 BEB，二進(jìn)制指數(shù)退避：流量控制二進(jìn)制退避技術(shù)（binary exponential backoff）. 指在遇到重復(fù)的沖突時(shí)，站點(diǎn)將重復(fù)傳輸，但在每一次沖突之后，隨著時(shí)延的平均值將加倍。二進(jìn)制指數(shù)退避可以依據(jù)通信環(huán)境的變化自適應(yīng)的調(diào)整沖突窗口值，提供了一個(gè)處理重負(fù)荷的方法。嘗試傳輸?shù)闹貜?fù)失敗導(dǎo)致更長(zhǎng)的退避時(shí)間，這將有助于負(fù)荷

5、的平滑。二進(jìn)制退避技術(shù)（binary exponential backoff）. 一旦檢測(cè)到?jīng)_突，為降低再?zèng)_突的概率，需要等待一個(gè)隨機(jī)時(shí)間，然后再使用CSMA方法試圖傳輸。為了保證這種退避維持穩(wěn)定，采用了二進(jìn)制指數(shù)退避算法的技術(shù)。沖突的窗口以2的指數(shù)次方增長(zhǎng)，讓站點(diǎn)隨機(jī)延遲一個(gè)時(shí)間點(diǎn)來(lái)發(fā)送，從而減小發(fā)生沖突的概率，這是一種自適應(yīng)算法.其算法過(guò)程如下：1. 將沖突發(fā)生后的時(shí)間劃分為長(zhǎng)度為2t的時(shí)隙2. 發(fā)生第一次沖突后，各個(gè)站點(diǎn)等待0或1個(gè)時(shí)隙再開(kāi)始重傳3. 發(fā)生第二次沖突后，各個(gè)站點(diǎn)隨機(jī)地選擇等待0，1，2或3個(gè)時(shí)隙再開(kāi)始重傳4. 第i次沖突后，在0至2的i次方減一間隨機(jī)地選擇一個(gè)等待的時(shí)隙數(shù)

6、，再開(kāi)始重傳5. 10次沖突后，選擇等待的時(shí)隙數(shù)固定在0至1023（2的10次方減一）間6. 16次沖突后，發(fā)送失敗，報(bào)告上層。例：若第二次發(fā)生碰撞：n = 2，k = MIN(2,10) = 2，R = 0, 1, 2, 3)，延遲時(shí)間 = 0, 51.2 , 102.4 , 153.6 us 其中任取一4、LPM(Longest-prefix Matching)最長(zhǎng)前綴匹配（可變長(zhǎng)網(wǎng)絡(luò)號(hào)）：路由表查找（最長(zhǎng)前綴匹配是指在IP協(xié)議中被路由器用于在路由表中進(jìn)行選擇的一個(gè)算法。因?yàn)槁酚杀碇械拿總€(gè)表項(xiàng)都指定了一個(gè)網(wǎng)絡(luò)，所以一個(gè)目的地址可能與多個(gè)表項(xiàng)匹配。最明確的一個(gè)表項(xiàng)，即子網(wǎng)掩碼最長(zhǎng)的一個(gè)，就叫

7、做最長(zhǎng)前綴匹配。）IP路由器查找轉(zhuǎn)發(fā)表或路由表：IP前綴與出口之間的映射關(guān)系。適用于單播路由：分組只有一個(gè)目標(biāo)地址；路由器查表，得到匹配項(xiàng)最長(zhǎng)前綴ib的表項(xiàng)及出口；關(guān)鍵問(wèn)題: 快速查找。5、CSMA載波偵聽(tīng)多址接入；多用戶接入（先聽(tīng)后說(shuō)）/CD（邊聽(tīng)邊說(shuō)）/CA（先聽(tīng)后說(shuō)） 隨機(jī)多址接入?yún)f(xié)議：ALOHA協(xié)議和CSMA協(xié)議。CSMA：以太網(wǎng)中，總線上只要有一臺(tái)計(jì)算機(jī)在發(fā)送數(shù)據(jù)，總線的傳輸資源就會(huì)被占用。所以在同一時(shí)間只允許一臺(tái)計(jì)算機(jī)發(fā)送信息，否則會(huì)發(fā)生沖突。載波偵聽(tīng)：每一站在發(fā)送數(shù)據(jù)之前要先檢測(cè)總線上是否有其他站在發(fā)送數(shù)據(jù)，若有則暫不發(fā)送，要等信道變?yōu)榭臻e時(shí)再發(fā)送。CSMA/CD：“邊說(shuō)邊聽(tīng)”。

8、首先檢查線路上是否有其他主機(jī)信號(hào)在發(fā)送:如果有，說(shuō)明其他主機(jī)在發(fā)送，自己利用退避算法等一會(huì)再試圖發(fā)送。如果沒(méi)有其他主機(jī)信號(hào)，自己則將數(shù)據(jù)發(fā)出去，同時(shí)不斷監(jiān)聽(tīng)線路，如果檢測(cè)到有其他信號(hào)，則自己發(fā)送一個(gè)阻塞信號(hào)，通知其他節(jié)點(diǎn)停止發(fā)送數(shù)據(jù)，自己也要停止發(fā)送數(shù)據(jù)，此時(shí)，再利用退避算法等一會(huì)再試圖發(fā)送。CSMA/CA：“先聽(tīng)后說(shuō)”。首先檢測(cè)介質(zhì)是否空閑，若是介質(zhì)為空閑時(shí)，送出RTS信號(hào)，接收端收到RTS信號(hào)后，將會(huì)送響應(yīng)信號(hào)CTS，當(dāng)發(fā)射端收到CTS包后，隨即開(kāi)始發(fā)送數(shù)據(jù)包。接收端收到數(shù)據(jù)包后，將以包內(nèi)的CRC校驗(yàn)碼來(lái)檢驗(yàn)包數(shù)據(jù)是否正確，若是檢驗(yàn)結(jié)果正確時(shí)，接收端將響應(yīng)ACK包，告知發(fā)射端數(shù)據(jù)己經(jīng)被成功

9、地接收。當(dāng)發(fā)射端沒(méi)有收到接收端的ACK包時(shí)，將認(rèn)為包在傳輸過(guò)程中丟失，將重新發(fā)送數(shù)據(jù)。CTS幀有兩個(gè)作用：一是表明接收節(jié)點(diǎn)B可以接收發(fā)送節(jié)點(diǎn)A的幀，二是禁止B的臨節(jié)點(diǎn)發(fā)送，從而避免了B的臨界點(diǎn)的發(fā)送對(duì)A到B的數(shù)據(jù)傳輸造成的影響。 6、 BHCA，忙時(shí)呼叫量：業(yè)務(wù)度量BHCA（Busy Hour Call Attempt，忙時(shí)每小時(shí)起呼次數(shù)）是通信業(yè)務(wù)工程中用于測(cè)量、評(píng)估和規(guī)劃電話網(wǎng)絡(luò)呼叫處理能力的一個(gè)關(guān)鍵性指標(biāo)。BHCA是指在一天中一個(gè)通信系統(tǒng)最繁忙的一個(gè)小時(shí)（高峰時(shí)期）電話呼叫的請(qǐng)求總次數(shù)。7、 ESR，誤碼秒（百分?jǐn)?shù)|率）：服務(wù)質(zhì)量指標(biāo)(以秒為單位)是指在一個(gè)確定的測(cè)試期間，在可用時(shí)間內(nèi)的

10、誤碼秒（ES）與總秒數(shù)之比。(SESR(Severely Errored Section Ratio)，嚴(yán)重誤碼秒率，是指在一個(gè)確定的測(cè)試期間，在可用時(shí)間內(nèi)的嚴(yán)重誤碼秒（SES）與總秒數(shù)之比。嚴(yán)重誤碼秒，是指含有30%誤碼秒或含有至少1個(gè)缺陷的1秒周期(BBER（Background Block Error Ratio），背景塊誤碼秒率，是指在一個(gè)確定的測(cè)試期間，在可用時(shí)間內(nèi)的背景誤碼秒，與總秒數(shù)中扣除嚴(yán)重誤碼秒中的所有秒數(shù)后剩余秒數(shù)之比。背景誤碼秒是指扣除在嚴(yán)重誤碼期間出現(xiàn)的嚴(yán)重誤碼秒之后所剩下的誤碼秒。8、 HDLC，高級(jí)數(shù)據(jù)鏈路控制：數(shù)據(jù)鏈路層的傳輸控制.完成功能：傳輸控制。做法：滑窗控

11、制高級(jí)數(shù)據(jù)鏈路控制（High-Level Data Link Control或簡(jiǎn)稱HDLC），是一個(gè)在同步網(wǎng)上傳輸數(shù)據(jù)、面向比特的數(shù)據(jù)鏈路層協(xié)議，它是由國(guó)際標(biāo)準(zhǔn)化組織（ISO）根據(jù)IBM公司的SDLC（Synchronous Data Link Control）協(xié)議擴(kuò)展開(kāi)發(fā)而成的。HDLC的完整的幀由標(biāo)志字段（F）、地址字段（A）、控制字段（C）、信息字段（I）、幀校驗(yàn)序列字段（FCS）等組成。HDLC特點(diǎn)：HDLC是面向比特的數(shù)據(jù)鏈路控制協(xié)議的典型代表，該協(xié)議不依賴于任何一種字符編碼集；數(shù)據(jù)報(bào)文可透明傳輸，用于實(shí)現(xiàn)透明傳輸?shù)摹?比特插入法”易于硬件實(shí)現(xiàn)； 全雙工通信，有較高的數(shù)據(jù)鏈路傳輸效率

12、；所有幀采用CRC檢驗(yàn)，對(duì)信息幀進(jìn)行順序編號(hào)，可防止漏收或重發(fā)，傳輸可靠性高；傳輸控制功能與處理功能分離，具有較大靈活性。標(biāo)志字段(F):標(biāo)志字段為01111110的比特模式，用以標(biāo)志幀的起始和前一幀的終止。地址字段(A)：的內(nèi)容取決于所采用的操作方式。命令幀中的地址字段攜帶的是對(duì)方站的地址，而響應(yīng)幀中的地址字段所攜帶的地址是本站的地址。控制字段(C)：控制字段用于構(gòu)成各種命令和響應(yīng)，以便對(duì)鏈路進(jìn)行監(jiān)視和控制?？刂谱侄沃械牡谝晃换虻谝弧⒌诙槐硎緜魉蛶念愋?，HDLC中有信息幀（I幀）、監(jiān)控幀（S幀）和無(wú)編號(hào)幀（U幀）三種不同類型的幀。控制字段的第五位是P/F位，即輪詢/終止（Poll/Fin

13、al）位?？刂谱侄沃械?或第1、2位表示傳送幀的類型，第1位為“0”表示是信息幀，第1、2位為“10”是監(jiān)控幀，“11”是無(wú)編號(hào)幀。信息字段(I)：信息字段可以是任意的二進(jìn)制比特串。幀校字段(FCS)：幀校驗(yàn)序列字段可以使用16位CRC，對(duì)兩個(gè)標(biāo)志字段之間的整個(gè)幀的內(nèi)容進(jìn)行校驗(yàn)。9、sliding window ，窗口控制：傳輸控制滑動(dòng)窗口協(xié)議是用來(lái)改善吞吐量的一種技術(shù)，即容許發(fā)送方在接收任何應(yīng)答之前傳送附加的包。接收方告訴發(fā)送方在某一時(shí)刻能送多少包（稱窗口尺寸）。發(fā)送方可以通過(guò)滑動(dòng)窗口的大小來(lái)確定應(yīng)該發(fā)送多少字節(jié)的數(shù)據(jù)。發(fā)送窗口用來(lái)對(duì)發(fā)送端進(jìn)行流量控制。發(fā)送窗口的大小Wt代表在還沒(méi)有收到對(duì)方

14、確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其丟棄。在連續(xù) ARQ 協(xié)議中，接收窗口的大小 Wr = 1。（只有當(dāng)收到的幀的序號(hào)與接收窗口一致時(shí)才能接收該幀。否則，就丟棄它。每收到一個(gè)序號(hào)正確的幀，接收窗口就向前（即向右方）滑動(dòng)一個(gè)幀的位置。同時(shí)發(fā)送對(duì)該幀的確認(rèn)。）TCP中采用滑動(dòng)窗口來(lái)進(jìn)行傳輸控制，滑動(dòng)窗口的大小意味著接收方還有多大的緩沖區(qū)可以用于接收數(shù)據(jù)。發(fā)送方可以通過(guò)滑動(dòng)窗口的大小來(lái)確定應(yīng)該發(fā)送多少字節(jié)的數(shù)據(jù)。10、Architecture,體系結(jié)構(gòu)/網(wǎng)架：網(wǎng)絡(luò)結(jié)構(gòu)ITU

15、-T HRX/HRP, 傳輸誤碼的分配；IBM SNA, 鏈路的可靠傳輸；E2E論斷, 通信子網(wǎng)與資源子網(wǎng)分割I(lǐng)SO OSI-RM, 分層協(xié)議結(jié)構(gòu)；ITU-T B-ISDN PRM, 三平面立體結(jié)構(gòu)11、E2E Arguments，端到端論斷：協(xié)議工程（端到端傳送功能的分布）：路由選擇：離不開(kāi)中間節(jié)點(diǎn)；差錯(cuò)控制：可以放在中間節(jié)點(diǎn)；安全控制：不宜放在中間節(jié)；只要在邊緣做就不放在網(wǎng)絡(luò)中間做點(diǎn)到點(diǎn)是物理拓?fù)?，是網(wǎng)絡(luò)層的。E2E：端到端是網(wǎng)絡(luò)連接，是運(yùn)輸層的。網(wǎng)絡(luò)要通信，必須建立連接，不管有多遠(yuǎn)，中間有多少機(jī)器，都必須在兩頭（源和目的）間建立連接，一旦連接建立起來(lái)，就說(shuō)已經(jīng)是端到端連接了，即端到端是邏

16、輯鏈路，這條路可能經(jīng)過(guò)了很復(fù)雜的物理路線，但兩端主機(jī)不管，并不知道中間節(jié)點(diǎn)的存在，只認(rèn)為是有兩端的連接，而且一旦通信完成，這個(gè)連接就釋放了，物理線路可能又被別的應(yīng)用用來(lái)建立連接了。TCP就是用來(lái)建立這種端到端連接的一個(gè)具體協(xié)議?？傊痪湓捀爬ň褪嵌说蕉耸怯蔁o(wú)數(shù)的點(diǎn)到點(diǎn)實(shí)現(xiàn)和組成的。只要能放在網(wǎng)絡(luò)邊緣做的就不要放在網(wǎng)絡(luò)中間做。E2E優(yōu)點(diǎn)：降低網(wǎng)絡(luò)核心復(fù)雜度，簡(jiǎn)化復(fù)雜功能；盡可能好的數(shù)據(jù)傳輸服務(wù)；“End-To-End”地址透明性和全球唯一地址。12、CIDR，無(wú)分類域間路由：路由與尋址CIDR（無(wú)類別域間路由，Classless Inter-Domain Routing）是一個(gè)在Interne

17、t上創(chuàng)建附加地址的方法，這些地址提供給服務(wù)提供商（ISP），再由ISP分配給客戶。CIDR將路由集中起來(lái)，使一個(gè)IP地址代表主要骨干提供商服務(wù)的幾千個(gè)IP地址，從而減輕Internet路由器的負(fù)擔(dān)。將32位的IP地址劃分為“網(wǎng)絡(luò)前綴”和“主機(jī)號(hào)”兩個(gè)部分。采用“斜線記法”，即在IP地址后面加上“/”，然后寫(xiě)上網(wǎng)絡(luò)前綴的位數(shù)，即地址掩碼中1的位數(shù)。13、STDM，統(tǒng)計(jì)時(shí)分復(fù)用：網(wǎng)絡(luò)資源共享STDM，統(tǒng)計(jì)時(shí)分復(fù)用，網(wǎng)絡(luò)資源共享，從統(tǒng)計(jì)上來(lái)說(shuō)是時(shí)分復(fù)用的。為了提高TDM系統(tǒng)的利用率,可以使用按需分配的技術(shù),即根據(jù)用戶需求動(dòng)態(tài)分配時(shí)隙,以避免每幀中出現(xiàn)空閑的時(shí)隙. STDM：是一種改進(jìn)的TDM，能明顯

18、的提高信道的利用率。各用戶有了數(shù)據(jù)就隨時(shí)發(fā)往集中器的輸入緩存，然后集中器按順序依次掃描輸入緩存，把緩存中的數(shù)據(jù)放入STDM幀中，對(duì)沒(méi)有數(shù)據(jù)的緩存就跳過(guò)，當(dāng)一個(gè)STDM幀的數(shù)據(jù)放滿了就發(fā)送出去。STDM幀不是固定分配時(shí)隙，而是按需動(dòng)態(tài)的分配時(shí)隙。在每個(gè)時(shí)隙中還必須有用戶的地址信息，這是STDM不可避免的開(kāi)銷。14、TCP，傳輸控制協(xié)議：端到端傳輸復(fù)用：傳輸層TCP（Transmission Control Protocol 傳輸控制協(xié)議）是一種面向連接的、可靠的、基于字節(jié)流的傳輸層通信協(xié)議，由IETF的RFC 793定義。在簡(jiǎn)化的計(jì)算機(jī)網(wǎng)絡(luò)OSI模型中，它完成第四層傳輸層所指定的功能。在因特網(wǎng)協(xié)

19、議族（Internet protocol suite）中，TCP層是位于IP層之上，應(yīng)用層之下的中間層。應(yīng)用層向TCP層發(fā)送用于網(wǎng)間傳輸?shù)?、?位字節(jié)表示的數(shù)據(jù)流，然后TCP把數(shù)據(jù)流分區(qū)成適當(dāng)長(zhǎng)度的報(bào)文段。之后TCP把結(jié)果包傳給IP層，由它來(lái)通過(guò)網(wǎng)絡(luò)將包傳送給接收端實(shí)體的TCP層。TCP為了保證不發(fā)生丟包，就給每個(gè)包一個(gè)序號(hào)，同時(shí)序號(hào)也保證了傳送到接收端實(shí)體的包的按序接收。然后接收端實(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用一個(gè)校驗(yàn)和函數(shù)來(lái)檢驗(yàn)數(shù)據(jù)是否有錯(cuò)誤；在發(fā)送和接收時(shí)都要

20、計(jì)算校驗(yàn)和。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)。三次握手完成，TCP客戶端和服務(wù)器端成功地建立連接，可以開(kāi)始傳輸數(shù)據(jù)了。15、CAC,呼叫接納控制：流量工程（CAC (Connection Admission Control)：連接接納控制是異步轉(zhuǎn)移模式（ATM）技術(shù)的一種流量控制標(biāo)準(zhǔn)。是網(wǎng)絡(luò)保護(hù)自身免受免受負(fù)荷威脅的第一道

21、防線。CAC通過(guò)限制進(jìn)入網(wǎng)絡(luò)的業(yè)務(wù)量來(lái)防止網(wǎng)絡(luò)中出現(xiàn)擁塞。CAC的功能可以概括為：確定接受或拒絕連接請(qǐng)求；選路及分配網(wǎng)絡(luò)資源；導(dǎo)出業(yè)務(wù)量合約中用于UPC/NPC的業(yè)務(wù)量參數(shù)。）僅對(duì)VoIP的業(yè)務(wù)流，不影響普通數(shù)據(jù)業(yè)務(wù)；對(duì)實(shí)時(shí)性或時(shí)延敏感的業(yè)務(wù)，依據(jù)網(wǎng)絡(luò)負(fù)載情況接收到阻止呼叫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ù)與否。16、DFS（Depth First Search，深度優(yōu)化搜索）：?jiǎn)尾ヂ酚伤惴?。?duì)每一個(gè)可能的分支路徑

22、深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次。步驟如下：（1）. 所有點(diǎn) x 關(guān)聯(lián)邊查找完成時(shí)，返回父節(jié)點(diǎn)；（2）. 否則選擇x的關(guān)聯(lián)邊e，到下一點(diǎn)y：如果y已查過(guò)，則e為回退邊；如果y未查過(guò)，e為樹(shù)邊，以y替代x重復(fù)第1步。17、MST（Minimum Spanning Tree，最小生成樹(shù)）：多播路由算法。一個(gè)有n個(gè)節(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，且包含原圖中所有n個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊，最小生成樹(shù)可以用Kruskal算法或Prim算法求解。Kruskal步驟：1. 將一條權(quán)最小的邊加入子圖 T 中，并保證不形成圈。2. 如果當(dāng)前弧加入后不形成圈，則加入這條弧，如果

23、當(dāng)前弧加入后會(huì)形成圈，則不加入這條弧，并考慮下一條弧。Prim步驟：1. 不斷擴(kuò)展一棵子樹(shù) T = (S , F), F 為E子集，直到S包括全部頂點(diǎn)，得到最小生成樹(shù)T。2. 每次增加一條邊，使得這條邊是由當(dāng)前子樹(shù)結(jié)點(diǎn)集S 及其補(bǔ)集S 所形成的邊割集的最小邊。途徑Walk：圖中存在關(guān)聯(lián)關(guān)系的點(diǎn)邊，交替出現(xiàn)的序列；跡Trail：無(wú)重復(fù)邊的walk；路Path：除始末點(diǎn)外無(wú)重復(fù)點(diǎn)的walk/trail。對(duì)圖G=(V,E)來(lái)說(shuō)，若G的兩個(gè)頂點(diǎn)u,v之間存在一條路徑，則稱u和v是連通的；若圖G的任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G是連通的。不包括回路的連通圖稱為樹(shù)。對(duì)于圖G=(V,E)，包含了圖G中所有頂

24、點(diǎn)的樹(shù)稱為生成樹(shù)。樹(shù)的等價(jià)定義：G=(V, E)是樹(shù)；G是連通的，且|E| = |V| - 1；G無(wú)圈，且|E| = |V| - 1；G的任意兩點(diǎn)之間，存在唯一條路；G是連通的，刪除任意一邊后為非連通；G無(wú)圈，增加任意一邊后，正好有一個(gè)圈。設(shè)圖G=(V, E)是連通圖，SE，若從圖G中消去屬于S的所有邊，則G變?yōu)橐粋€(gè)非連通的圖；而若去掉屬于S的任何真子集中的邊，圖G仍保持連通，則稱S是圖的G的一個(gè)割集。即割集S是使連通圖G失去連通性的最小的邊的集合。18距離矢量路由控制：計(jì)算機(jī)網(wǎng)絡(luò)通常使用動(dòng)態(tài)路由算法，這些算法能找到當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的最短路徑，其中最流行的動(dòng)態(tài)路由算法是距離矢量路由算法和鏈路

25、狀態(tài)路由算法。距離矢量路由算法中，每個(gè)路由器維護(hù)一張表（一個(gè)矢量），表中列出了當(dāng)前已知的到每個(gè)目標(biāo)的最佳距離，以及所使用的鏈路。這些表通過(guò)鄰居之間的相互交換信息二不斷被更新，最終每個(gè)路由器都了解到達(dá)目的地的最佳鏈路。路由器從自己的鄰居路由器得到路由信息，并將這些路由信息連同自己的本地路由信息發(fā)送給其他鄰居，這樣一級(jí)級(jí)的傳遞下去以達(dá)到全網(wǎng)同步。每個(gè)路由器都不了解整個(gè)網(wǎng)絡(luò)拓?fù)?，它們只知道與自己直接相連的網(wǎng)絡(luò)情況，并根據(jù)從鄰居得到的路由信息更新自己的路由。RIP（Routing Information Protocol，路由信息協(xié)議）、參考方法8： 工作原理：(1)路由建立:路由器運(yùn)行RIP后，會(huì)首

26、先發(fā)送路由更新請(qǐng)求，收到請(qǐng)求的路由器會(huì)發(fā)送自己的RIP路由進(jìn)行響應(yīng)(2)距離矢量的計(jì)算:RIP度量的單位是跳數(shù)，其單位是1，也就是規(guī)定每一條鏈路的成本為1，而不考慮鏈路的實(shí)際帶寬、時(shí)延等因素，RIP最多允許15跳。(3)定時(shí)器:周期更新定時(shí)器；超時(shí)定時(shí)器；清除定時(shí)器； 延遲定時(shí)器。(4)環(huán)路:當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí)，RIP網(wǎng)絡(luò)有可能產(chǎn)生路由環(huán)路?？梢酝ㄟ^(guò)水平分割、毒性反轉(zhuǎn)、觸發(fā)更新、抑制時(shí)間等技術(shù)來(lái)避免環(huán)路的產(chǎn)生。距離相等路徑的解決方法（1） 先到先用；（2） 組播更新周期一半之前的優(yōu)先。19、OSPF（Open Shortest Path First,開(kāi)放最短路徑優(yōu)先）：鏈路狀態(tài)路由。工作原理：每

27、臺(tái)路由器通過(guò)使用Hello報(bào)文與它的鄰居之間建立鄰接關(guān)系 ；每臺(tái)路由器向每個(gè)鄰居發(fā)送鏈路狀態(tài)通告(LSA),有時(shí)叫鏈路狀態(tài)報(bào)文(LSP). 每個(gè)鄰居在收到LSP之后要依次向它的鄰居轉(zhuǎn)發(fā)這些LSP(泛洪) ；每臺(tái)路由器要在數(shù)據(jù)庫(kù)中保存一份它所收到的LSA的備份，所有路由器的數(shù)據(jù)庫(kù)應(yīng)該相同 ；依照拓?fù)鋽?shù)據(jù)庫(kù)每臺(tái)路由器使用Dijkstra算法（SPF算法）計(jì)算出到每個(gè)網(wǎng)絡(luò)的最短路徑，并將結(jié)果輸出到路由選擇表中。OSPF的簡(jiǎn)化原理：發(fā)Hello報(bào)文建立鄰接關(guān)系形成鏈路狀態(tài)數(shù)據(jù)庫(kù)SPF算法形成路由表。相同點(diǎn)：都是動(dòng)態(tài)路由協(xié)議；都是內(nèi)部路由協(xié)議（即在AS內(nèi)運(yùn)行）；都支持VLSM（變長(zhǎng)子網(wǎng)掩碼）；都是組播更

28、新，支持認(rèn)證。不同點(diǎn)：RIP是按跳數(shù)來(lái)算路由的，OSPF是狀態(tài)路由協(xié)議；兩個(gè)路由協(xié)議支持跳數(shù)大小不一樣。RIPOSPF默認(rèn)開(kāi)啟自動(dòng)匯總，匯總路由基于接口區(qū)域默認(rèn)沒(méi)有匯總，匯總路由基于區(qū)域支持接口明文或MD5認(rèn)證支持區(qū)域和接口明文或MD5認(rèn)證周期更新，匯聚時(shí)間長(zhǎng)，更新不及時(shí)會(huì)有環(huán)路觸發(fā)更新，快速匯聚，無(wú)環(huán)路開(kāi)銷以跳數(shù)為單位，不識(shí)別帶寬運(yùn)行SPF算法計(jì)算開(kāi)銷，識(shí)別帶寬周期更新整張路由表，開(kāi)銷大區(qū)域內(nèi)交換LSA構(gòu)建LSDB，開(kāi)銷小20、LAN廣播風(fēng)暴：由于網(wǎng)絡(luò)中有環(huán)路存在，造成每一幀都在網(wǎng)絡(luò)中重復(fù)廣播，獲得了更多的響應(yīng)，以至于像滾雪球一樣，導(dǎo)致網(wǎng)絡(luò)癱瘓，引起了廣播風(fēng)暴。要消除這種網(wǎng)絡(luò)循環(huán)連接帶來(lái)的網(wǎng)

29、絡(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（Spanning Tree Protocol.生成樹(shù)協(xié)議）：STP：樹(shù)是不包括回路（環(huán)）的連通圖，對(duì)于圖,包含了圖G中所有頂點(diǎn)的樹(shù)成為生成樹(shù)。生成樹(shù)協(xié)議拓?fù)浣Y(jié)構(gòu)的思路是: 不論網(wǎng)橋(交換機(jī))之間采用怎樣物理聯(lián)接,網(wǎng)橋(交換機(jī))能夠自動(dòng)發(fā)現(xiàn)一個(gè)沒(méi)有環(huán)路的拓?fù)浣Y(jié)構(gòu)的網(wǎng)路，這個(gè)邏輯拓?fù)浣Y(jié)構(gòu)的網(wǎng)路必須是樹(shù)型的。生成樹(shù)協(xié)議還能夠確定有足夠的連接通向整個(gè)網(wǎng)絡(luò)的每一個(gè)部分。所有網(wǎng)絡(luò)節(jié)點(diǎn)要么進(jìn)入轉(zhuǎn)發(fā)狀態(tài)，要么進(jìn)入阻塞狀態(tài),這樣就建立了整

30、個(gè)局域網(wǎng)的生成樹(shù)。當(dāng)首次連接網(wǎng)橋或者網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)，網(wǎng)橋都將進(jìn)行生成樹(shù)拓?fù)涞闹匦掠?jì)算。為穩(wěn)定的生成樹(shù)拓?fù)浣Y(jié)構(gòu)選擇一個(gè)根橋, 從一點(diǎn)傳輸數(shù)據(jù)到另一點(diǎn), 出現(xiàn)兩條以上條路徑時(shí)只能選擇一條距離根橋最短的活動(dòng)路徑。生成樹(shù)協(xié)議這樣的控制機(jī)制可以協(xié)調(diào)多個(gè)網(wǎng)橋(交換機(jī))共同工作, 使計(jì)算機(jī)網(wǎng)絡(luò)可以避免因?yàn)橐粋€(gè)接點(diǎn)的失敗導(dǎo)致整個(gè)網(wǎng)絡(luò)聯(lián)接功能的丟失, 而且冗余設(shè)計(jì)的網(wǎng)絡(luò)環(huán)路不會(huì)出現(xiàn)廣播風(fēng)暴。（1）選擇根網(wǎng)橋：再全網(wǎng)中選擇一個(gè)根網(wǎng)橋：BID最小的被選舉為根網(wǎng)橋。（2）選擇根端口：在每個(gè)非根交換機(jī)上選擇根端口：路徑成本最低的端口為根端口；路徑成本相同，BID較小的優(yōu)先極高，稱為根端口。（3）選擇指定端口：在每條

31、鏈路上選擇一個(gè)指定端口，根網(wǎng)橋上所有端口都是指定端口。21、約束路由計(jì)算方法約束路由是一種命令驅(qū)動(dòng)并具有資源預(yù)留能力的路由算法，能夠和現(xiàn)有的 Internet 中的拓?fù)潋?qū)動(dòng)的、逐跳的內(nèi)部網(wǎng)關(guān)協(xié)議共存。它可以根據(jù)多個(gè)約束條件（可以是QOS 約束條件也可以是其他策略性的約束條件）計(jì)算出所有的可能路徑并根據(jù)一定的優(yōu)選策略選出一條最優(yōu)的路徑，實(shí)現(xiàn)網(wǎng)絡(luò)性能的優(yōu)化。（延時(shí)、帶寬、跳數(shù)約束等）在一個(gè)源點(diǎn)到其他網(wǎng)絡(luò)節(jié)點(diǎn)間首先找到一條最小跳數(shù)的路由，且該路由受約束。QoS多約束包括帶寬、緩沖、延時(shí)、抖動(dòng)和丟包等約束條件，為了找到一條滿足多約束條件的路徑，先搜索相同跳數(shù)時(shí)是否存在滿足多約束條件的路徑，如果沒(méi)找到，

32、增加一跳繼續(xù)搜索滿足多約束條件的路徑，不斷迭代，直到找到一個(gè)折中點(diǎn)，使這條路徑能夠同時(shí)滿足約束條件。流量工程：繞過(guò)網(wǎng)絡(luò)中已知的瓶頸和阻塞點(diǎn)，將業(yè)務(wù)映射到現(xiàn)有拓?fù)渖系臉I(yè)務(wù)，將成為ISP（Internet service provider）們一個(gè)非常重要的工具；ISP必須配置一個(gè)能夠使他們的客戶連接到他們網(wǎng)絡(luò)上的物理拓?fù)浣Y(jié)構(gòu)。在網(wǎng)絡(luò)部署完畢后，ISP必須將客戶的業(yè)務(wù)流映射到網(wǎng)絡(luò)的物理拓?fù)渖?。LSR通過(guò)對(duì)TED中的信息使用CSPF算法決定每條LSP的物理路徑。CSPF（ConstrainedShortest Path First約束最短路徑優(yōu)先）：CSPF是一種改進(jìn)的最短路徑優(yōu)先算法，它是一種在計(jì)算

33、通過(guò)網(wǎng)絡(luò)的最短路徑時(shí)，將特定的約束也考慮進(jìn)去的算法，用于對(duì)流量的控制。屬性格式(鏈路，代價(jià)，下一跳，可用帶寬)（1）,選擇擁有最大的預(yù)留帶寬的路徑。（2），如果二者仍然相同，選擇具有最小跳數(shù)的路徑。(路徑中三層設(shè)備的個(gè)數(shù))（3）, 如果仍然相同，隨機(jī)選擇一條（那么選擇PATH列表置頂?shù)穆窂剑?2、MMPP（Markov modulated Poisson process，馬氏調(diào)制泊松過(guò)程）：是一種雙隨機(jī)過(guò)程，這種調(diào)制過(guò)程強(qiáng)度是有一個(gè)馬爾科夫鏈來(lái)調(diào)制，當(dāng)鏈的狀態(tài)是i的時(shí)候，我們稱相位為i，強(qiáng)度取,i=1，2N,這里N是調(diào)制鏈的狀態(tài)數(shù)。因此MMPP是由用以調(diào)制的馬爾科夫鏈的無(wú)窮小生成矩陣和一個(gè)泊松

34、過(guò)程的強(qiáng)度向量所唯一確定的。排隊(duì)論(Queuing Theory)：是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)服務(wù)系統(tǒng)工作過(guò)程的數(shù)學(xué)理論和方法，又稱隨機(jī)服務(wù)系統(tǒng)理論，為運(yùn)籌學(xué)的一個(gè)分支。23、語(yǔ)義透明：語(yǔ)義透明是業(yè)務(wù)傳送的需求，要求信息在通信過(guò)程中，信息內(nèi)容不被改變，在實(shí)際通信中，為了實(shí)現(xiàn)語(yǔ)義透明，需要采用很多措施，對(duì)于誤碼、丟失、誤插，需要采用流量控制及差錯(cuò)控制解決，對(duì)于編碼問(wèn)題，采用轉(zhuǎn)義控制來(lái)解決，在語(yǔ)義透明中，信息量是核心問(wèn)題。解決方案：信道中噪聲的干擾會(huì)增大誤碼率，可以通過(guò)增加信號(hào)功率增大信噪比；資源有限造成阻塞和擁擠，使得一些信息丟失，可以根據(jù)系統(tǒng)的性能合理進(jìn)行流量控制。舉例：電子轉(zhuǎn)賬要求實(shí)際無(wú)差

35、錯(cuò)的信息傳遞來(lái)保證金融信息傳送的正確性，這種端到端的質(zhì)量的提高可以用二種技術(shù)來(lái)實(shí)現(xiàn)，一種是前向差錯(cuò)糾錯(cuò)，（3選2）擇多判決，發(fā)送方發(fā)送多次相同的信息則認(rèn)為發(fā)送正確，稱為自動(dòng)重發(fā)。另一種是后向糾錯(cuò)，利用所謂自動(dòng)重發(fā)請(qǐng)求協(xié)議在檢測(cè)到錯(cuò)誤后，接受方要求發(fā)送方重傳。時(shí)間透明：時(shí)間透明也是業(yè)務(wù)傳送的需求，要求信息在通信過(guò)程中，可以被無(wú)延遲地送到，強(qiáng)調(diào)通信的實(shí)時(shí)性，對(duì)通信過(guò)程的控制，產(chǎn)生技術(shù)性約束，在實(shí)現(xiàn)時(shí)間透明中，糾錯(cuò)和嵌入式技術(shù)，是核心問(wèn)題。24、單純形法：求解線性規(guī)劃問(wèn)題的通用方法。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所

36、對(duì)應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。網(wǎng)絡(luò)單純形法：最小生成樹(shù)求解。找最小生成樹(shù)構(gòu)成環(huán)的邊，從環(huán)里面增加一條新邊，減掉一條舊邊，就構(gòu)成了樹(shù)的變化，對(duì)應(yīng)于單純形法中凸點(diǎn)之間的轉(zhuǎn)換。找到一條合適的新邊加入原有生成樹(shù)，以便于這條生成樹(shù)的成本降低。同時(shí)從原來(lái)的環(huán)里去除一條舊邊，才能構(gòu)造一棵新的生成樹(shù)，因?yàn)闃?shù)是不允許有環(huán)的。思路：（1）以一個(gè)初始生成樹(shù)為起點(diǎn)（

37、該生成樹(shù)包含網(wǎng)絡(luò)的所有節(jié)點(diǎn)）；（2）可行樹(shù)解x與生成樹(shù)T相關(guān)聯(lián)，且xij=0, if ij不是生成樹(shù)T的邊；（3）通過(guò)查找所有可行樹(shù)解，得最優(yōu)解。因?yàn)?，加入?shù)外的邊，必然增大成本。25、易損期：易損期是吞吐性能求解的一個(gè)參數(shù)，表示在兩個(gè)分組發(fā)送期間會(huì)發(fā)生沖突的時(shí)間。在下圖中，第一個(gè)分組開(kāi)始發(fā)送的時(shí)刻是t,分組發(fā)送時(shí)長(zhǎng)是T，在t+T時(shí)刻，第二個(gè)分組開(kāi)始發(fā)送，那么易損期就是t-T到t+T之間的2T時(shí)間間隔。26.剩余服務(wù)時(shí)間：剩余服務(wù)時(shí)間在M/G/1求解問(wèn)題中常用到的一個(gè)參數(shù)，在M/G/1模型中，用戶到達(dá)人數(shù)服從泊松分布，服務(wù)時(shí)間相同且為任意分布，只有一個(gè)服務(wù)員，在這種情況下，第i個(gè)顧客等待服務(wù)的

38、時(shí)間可以表示為，這里的表示在第i個(gè)顧客之前等待的顧客數(shù)目，S表示平均的服務(wù)時(shí)間，R表示服務(wù)員的剩余服務(wù)時(shí)間。如果服務(wù)員處于空閑狀態(tài)，那么R=0，否則表示某一個(gè)顧客接受服務(wù)的剩余服務(wù)時(shí)間。1、面向連接服務(wù)：面向連接的服務(wù)（connection-oriented service）就是通信雙方在通信時(shí),要事先建立一條通信線路,其過(guò)程有建立連接、使用連接和釋放連接三個(gè)過(guò)程。TCP協(xié)議就是一種面向連接服務(wù)的協(xié)議,電話系統(tǒng)是一個(gè)面向連接的模式。無(wú)連接服務(wù)：無(wú)連接服務(wù)就是通信雙方不需要事先建立一條通信線路，而是把每個(gè)帶有目的地址的包（報(bào)文分組）送到線路上，由系統(tǒng)選定路線進(jìn)行傳輸。IP、UDP協(xié)議就是一種無(wú)連

39、接協(xié)議，郵政系統(tǒng)是一個(gè)無(wú)連接的模式。A.TCP是面向連接的運(yùn)輸層協(xié)議，在傳送數(shù)據(jù)之前必須先建立連接，數(shù)據(jù)傳送之后要釋放連接；每一條TCP只能有兩端點(diǎn)，即每一條TCP連接只能是點(diǎn)對(duì)點(diǎn)的；提供可靠交付的服務(wù)；提供雙工通信；面向字節(jié)流。由于 TCP 要提供可靠的、面向連接的運(yùn)輸服務(wù)，因此不可避免地增加了許多的開(kāi)銷，如確認(rèn)、流量控制、計(jì)時(shí)器及連接管理等f(wàn)。這不僅使協(xié)議數(shù)據(jù)單元的首部增大很多，還要占用許多的處理機(jī)資源。B.UDP 是無(wú)連接的，無(wú)連接服務(wù)就是通信雙方不需要事先建立一條通信線路，而是把每個(gè)帶有目的地址的包（報(bào)文分組）送到線路上，由系統(tǒng)選定路線進(jìn)行傳輸。發(fā)送數(shù)據(jù)之前不需要建立連接，減少了開(kāi)銷和

40、發(fā)送數(shù)據(jù)之前的時(shí)延；使用盡最大努力交付，即不保證可靠交付，同時(shí)不使用流量控制和擁塞控制，因此主機(jī)不需要維持具有許多參數(shù)的、復(fù)雜的鏈路狀態(tài)表；由于UDP沒(méi)有擁塞控制，因此網(wǎng)絡(luò)出現(xiàn)的擁塞不會(huì)使源主機(jī)的發(fā)送速率降低；是面向報(bào)文的；支持一對(duì)一、一對(duì)多、多對(duì)一和多對(duì)多的交互通信；用戶數(shù)據(jù)報(bào)只有8個(gè)字節(jié)的首部開(kāi)銷，比TCP的20個(gè)字節(jié)的首部要短的多。2.前向糾錯(cuò)的計(jì)算方法。為了提高時(shí)間透明性，用戶應(yīng)盡可能降低傳輸錯(cuò)誤。所以在通信里面通常采用前向糾錯(cuò)做法，以便減少接收出錯(cuò)的情況。前向糾錯(cuò)也叫前向糾錯(cuò)碼(Forward Error Correction簡(jiǎn)稱FEC)，是增加數(shù)據(jù)通訊可信度的方法。在單向通訊信道中

41、，一旦錯(cuò)誤被發(fā)現(xiàn)，其接收器將無(wú)權(quán)再請(qǐng)求傳輸。FEC 是利用數(shù)據(jù)進(jìn)行傳輸冗長(zhǎng)信息的方法，當(dāng)傳輸中出現(xiàn)錯(cuò)誤，將允許接收器再建數(shù)據(jù)。常用的檢錯(cuò)方法有兩類：一類是奇偶校驗(yàn)，另一類是循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check）。其基本思路是發(fā)端按照給定的規(guī)則在K個(gè)信息比特后面增加L個(gè)按照某種規(guī)則計(jì)算的校驗(yàn)比特，在接收端對(duì)收到的信息比特重新計(jì)算L個(gè)校驗(yàn)比特。比較接收到的校驗(yàn)比特和本地重新計(jì)算的校驗(yàn)比特，如果相同則認(rèn)為傳輸無(wú)誤，否則認(rèn)為傳輸有錯(cuò)。(奇偶校驗(yàn)碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡(jiǎn)單和廣泛采用的方法。是一種通過(guò)增加冗余位使得碼字中"1"的個(gè)數(shù)恒為奇數(shù)或偶數(shù)

42、的編碼方法，它是一種檢錯(cuò)碼。在實(shí)際使用時(shí)又可分為垂直奇偶校驗(yàn)、水平奇偶校驗(yàn)和水平垂直奇偶校驗(yàn)等幾種。奇偶校驗(yàn)可描述為：給每一個(gè)碼字加一個(gè)校驗(yàn)位，用它來(lái)構(gòu)成奇性或偶性校驗(yàn)?？梢钥闯?，附加碼元d2，是簡(jiǎn)單地用來(lái)使每個(gè)字成為偶性的。因此，若有一個(gè)碼元是錯(cuò)的，就可以分辨得出，因?yàn)槠媾夹ｒ?yàn)將成為奇性。奇偶校驗(yàn)編碼通過(guò)增加一位校驗(yàn)位來(lái)使編碼中1個(gè)個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或者為偶數(shù)（偶校驗(yàn)），從而使碼距變?yōu)?。因?yàn)槠淅玫氖蔷幋a中1的個(gè)數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。(CRC的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼也叫（N，K）碼。對(duì)于一個(gè)給定的（N，K）碼

43、，可以證明存在一個(gè)最高次冪為N-K=R的多項(xiàng)式G(x)。根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。校驗(yàn)碼的具體生成過(guò)程為：假設(shè)要發(fā)送的信息用多項(xiàng)式C(X)表示，將C(x)左移R位（可表示成C(x)*xR），這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。用 C(x)*xR 除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。2、后向反饋的滑窗控制：在回退n幀的ARQ中，當(dāng)發(fā)送方接收到接收方的狀態(tài)報(bào)告指示報(bào)文出錯(cuò)后，發(fā)送方將重傳過(guò)去的n個(gè)報(bào)文。在回退N ARQ中，發(fā)送窗口大于1，接收窗口等于1，也就是說(shuō)發(fā)送方在發(fā)送完一個(gè)數(shù)據(jù)幀后，不停下來(lái)等待應(yīng)答幀，而是

44、連續(xù)發(fā)送若干個(gè)數(shù)據(jù)幀，即使在連續(xù)發(fā)送過(guò)程中收到了接收方發(fā)來(lái)的應(yīng)答幀，也可以繼續(xù)發(fā)送，但是，一旦某幀發(fā)生錯(cuò)誤，必須重新發(fā)送該幀及其后的n幀。最大窗口大小為2n-1。3、比特填充：在HDLC的幀結(jié)構(gòu)中，若在兩個(gè)標(biāo)志字段之間的比特串中，碰巧出現(xiàn)了和標(biāo)志字段F（01111110）一樣的比特組合，那么就會(huì)誤認(rèn)為是幀的邊界。為了避免出現(xiàn)這種情況，HDLC采用零比特填充法使一幀中兩個(gè)F字段之間不會(huì)出現(xiàn)6個(gè)連續(xù)1。零比特填充法的具體做法是：在發(fā)送端，當(dāng)一串比特流尚未加上標(biāo)志字段時(shí)，先用掃描整個(gè)幀。只要發(fā)現(xiàn)5個(gè)連續(xù)1，則立即填入一個(gè)0。因此經(jīng)過(guò)這種零比特填充后的數(shù)據(jù)，就可以保證不會(huì)出現(xiàn)6個(gè)連續(xù)1。在接收一個(gè)幀時(shí)

45、，先找到F字段以確定幀的邊界。接著再對(duì)其中的比特流進(jìn)行掃描。每當(dāng)發(fā)現(xiàn)5個(gè)連續(xù)1時(shí)，就將這5個(gè)連續(xù)1后的一個(gè)0刪除，以還原成原來(lái)的比特流。這樣就保證了在所傳送的比特流中，不管出現(xiàn)什么樣的比特組合，也不至于引起幀邊界的判斷錯(cuò)誤。4、Aloha隨機(jī)多址接入控制： 若一個(gè)空閑的節(jié)點(diǎn)有一個(gè)分組到達(dá)，就立即發(fā)送該分組，并期望不會(huì)和其他節(jié)點(diǎn)發(fā)生碰撞。分為純ALOHA和時(shí)隙ALOHA。純ALOHA：“想說(shuō)就說(shuō)”。網(wǎng)絡(luò)中多個(gè)用戶共用一個(gè)信道，采用競(jìng)爭(zhēng)方式，各自隨機(jī)的訪問(wèn)系統(tǒng)。站點(diǎn)只要產(chǎn)生幀，就立即發(fā)送到信道上；規(guī)定時(shí)間內(nèi)若收到應(yīng)答，表示發(fā)送成功，否則等待一段隨機(jī)時(shí)間，然后重發(fā)；若再次沖突，則再等待一段隨機(jī)時(shí)間，

46、直到發(fā)送成功為止。由于產(chǎn)生沖突現(xiàn)象，使傳輸效率或吞吐率降低。只有在易受破壞區(qū)間（易損期）內(nèi)沒(méi)有其他分組傳輸，該分組才能成功傳輸。時(shí)隙ALOHA：將時(shí)間軸劃分為若干個(gè)時(shí)隙（寬度等于一個(gè)分組的傳輸時(shí)間），各節(jié)點(diǎn)只能在時(shí)隙的開(kāi)始時(shí)刻才能發(fā)送分組。（假設(shè)系統(tǒng)有無(wú)窮多個(gè)節(jié)點(diǎn)，重傳的時(shí)延足夠隨機(jī)，重傳分組和新到達(dá)分組合成的分組流是到達(dá)率為G的Poisson過(guò)程，則，G=t，在t時(shí)長(zhǎng)內(nèi)，t是時(shí)間段，指平均的發(fā)生事件的數(shù)量。在易損期內(nèi)沒(méi)有其他分組傳輸?shù)母怕剩磌=0時(shí)的概率，對(duì)于純ALOHA來(lái)說(shuō)易損期為2T，P(0)=e-2G，吞吐量S=Ge-2G，求導(dǎo)后可得最大通過(guò)率約為0.184，G=0.5時(shí)；對(duì)于時(shí)隙A

47、LOHA最大通過(guò)率約為0.368，G=1時(shí)。）。5、CSMA/(CD/CA)隨機(jī)多址接入控制：（1）CD: (邊聽(tīng)邊說(shuō))首先檢查線路上是否有其他主機(jī)信號(hào)在發(fā)送:如果有，說(shuō)明其他主機(jī)在發(fā)送，自己利用退避算法等一會(huì)再試圖發(fā)送。如果沒(méi)有其他主機(jī)信號(hào)，自己則將數(shù)據(jù)發(fā)出去，同時(shí)不斷監(jiān)聽(tīng)線路，如果檢測(cè)到有其他信號(hào)，則自己發(fā)送一個(gè)阻塞信號(hào)，通知其他節(jié)點(diǎn)停止發(fā)送數(shù)據(jù)，自己也要停止發(fā)送數(shù)據(jù)，此時(shí)，再利用退避算法等一會(huì)再試圖發(fā)送。（2）CA: (先聽(tīng)再說(shuō))首先檢測(cè)介質(zhì)是否空閑，若是介質(zhì)為空閑時(shí)，送出RTS信號(hào)，接收端收到RTS信號(hào)后，將會(huì)送響應(yīng)信號(hào)CTS，當(dāng)發(fā)射端收到CTS包后，隨即開(kāi)始發(fā)送數(shù)據(jù)包。接收端收到數(shù)據(jù)

48、包后，將以包內(nèi)的CRC校驗(yàn)碼來(lái)檢驗(yàn)包數(shù)據(jù)是否正確，若是檢驗(yàn)結(jié)果正確時(shí)，接收端將響應(yīng)ACK包，告知發(fā)射端數(shù)據(jù)己經(jīng)被成功地接收。當(dāng)發(fā)射端沒(méi)有收到接收端的ACK包時(shí)，將認(rèn)為包在傳輸過(guò)程中丟失，將重新發(fā)送數(shù)據(jù)。6、電話呼叫的固定等級(jí)制路由選擇： 1.星型匯接：構(gòu)成基干路由。由同一交換區(qū)內(nèi)相鄰等級(jí)交換中心的低呼損電路群所組成，在該路由上的話務(wù)量不允許溢出到其他路由。2.相鄰直連：提供高效直達(dá)路由。它是由任意兩個(gè)等級(jí)交換中心之間高效電路群所組成的路由，可以全部或部分地旁路基干路由，在該路由上的話務(wù)量可以溢出到其他路由。 1）路由選擇的基本原則：首先，路由選擇應(yīng)確保傳輸質(zhì)量和信令信號(hào)的可靠傳輸。最長(zhǎng)的串接段

49、不應(yīng)超過(guò)7段。其次，路由選擇方法應(yīng)有明確的規(guī)律性，不出現(xiàn)死循環(huán)。第三，不應(yīng)使網(wǎng)絡(luò)設(shè)計(jì)或?qū)粨Q設(shè)備的要求過(guò)于復(fù)雜，首選串接段數(shù)少的路由。最后，能在低等級(jí)網(wǎng)絡(luò)中疏通的話務(wù)量，盡量不在高等級(jí)交換中心疏通。2）等級(jí)制路由選擇規(guī)則：在我國(guó)最早實(shí)行的路由選擇規(guī)則規(guī)定：一個(gè)交換中心呼叫某一目標(biāo)局的路由，其中路徑數(shù)最大為3個(gè)；有高效直達(dá)路由時(shí)，路由選擇順序依次為高效直達(dá)路由、迂回路由、基干路由；無(wú)高效直達(dá)路由時(shí)，路由選擇順序?yàn)榭缂?jí)或跨區(qū)的路由、基干路由；一般在受話區(qū)自下(下級(jí)局)而上(上級(jí)層)，發(fā)話區(qū)自上而下；在跨區(qū)路由中，連接該路由的兩個(gè)交換中心的等級(jí)差不應(yīng)超過(guò)一級(jí)，但在選擇跨級(jí)路由時(shí)，允許連接該路由上的兩

50、個(gè)交換中心的等級(jí)差不超過(guò)二級(jí)；路由選擇過(guò)程中，遇到低呼損路由時(shí)，不再溢出，路由選擇終止。7、距離矢量路由控制： 路由器從自己的鄰居路由器得到路由信息，并將這些路由信息連同自己的本地路由信息發(fā)送給其他鄰居，這樣一級(jí)級(jí)的傳遞下去以達(dá)到全網(wǎng)同步。每個(gè)路由器都不了解整個(gè)網(wǎng)絡(luò)拓?fù)?，它們只知道與自己直接相連的網(wǎng)絡(luò)情況，并根據(jù)從鄰居得到的路由信息更新自己的路由。由于每一個(gè)路由器都要維護(hù)從它自己到其他每一個(gè)目的網(wǎng)絡(luò)的距離記錄，即距離向量，相鄰的路由器間交換的也是各自的距離向量，最后各自根據(jù)路由器的距離向量來(lái)更新自己的距離向量，因此這類路由選擇算法被稱為距離向量路由選擇算法。RIP協(xié)議的距離向量算法：收到相鄰路

51、由器（其地址為 X）的一個(gè)路由更新報(bào)文：(1) 先修改此報(bào)文中的所有項(xiàng)目：把“下一跳”字段中的地址都改為X，并把所有的“距離”字段的值加1。每一個(gè)項(xiàng)目都有三個(gè)關(guān)鍵數(shù)據(jù)，即：到目的網(wǎng)絡(luò)N，距離是d，下一跳路由器是X。(2) 若原路由表中沒(méi)有目的網(wǎng)絡(luò)N，則把該項(xiàng)目添加到路由表中。否則，查看路由表中目的網(wǎng)絡(luò)為N的表項(xiàng)，若其下一跳是X，則把收到的項(xiàng)目替換原項(xiàng)目。否則，若收到的項(xiàng)目中的距離d小于路由表中的距離，則進(jìn)行更新，否則什么也不做。(3) 若180秒（默認(rèn)）沒(méi)有收到某條路由項(xiàng)目的更新報(bào)文，則把該路由項(xiàng)目記為無(wú)效，即把距離置為16（距離為16表示不可達(dá)），若再過(guò)一段時(shí)間，如120秒，還沒(méi)有收到該路由

52、項(xiàng)目的更新報(bào)文，則將該路由項(xiàng)目從路由表中刪除。(4) 若路由表發(fā)生變化，向所有相鄰路由器發(fā)送路由更新報(bào)文。(5) 返回。RIP協(xié)議讓互聯(lián)網(wǎng)中的所有路由器都和自己的相鄰路由器不斷交換路由信息，并不斷更新其路由表，使得從每一個(gè)路由器到每一個(gè)目的網(wǎng)絡(luò)的路由都是最短的（即跳數(shù)最少）。雖然所有的路由器最終都擁有了整個(gè)自治系統(tǒng)的全局路由信息，但由于每一個(gè)路由器的位置不同，它們的路由表當(dāng)然也應(yīng)當(dāng)是不同的。RIP 協(xié)議采用的是距離向量路由選擇算法，三個(gè)要點(diǎn)（1）僅和相鄰路由器交換信息。 （2）交換的信息是當(dāng)前本路由器所知道的全部信息，即自己的路由表。 （3）按固定的時(shí)間間隔交換路由信息（即周期性更新），例如，

53、每隔 30 秒。然后路由器根據(jù)收到的路由信息更新路由表。為加快協(xié)議的收斂速度，當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，路由器也及時(shí)向相鄰路由器通告拓?fù)渥兓蟮穆酚尚畔ⅲ从|發(fā)更新）。路由器收到相鄰路由器發(fā)送給他的路由信息（即距離向量）后，判斷從哪個(gè)相鄰路由器或直接到某個(gè)網(wǎng)絡(luò)的距離最近，從而找出每個(gè)目的網(wǎng)絡(luò)的最短距離和下一跳路由器，最后更新路由表。RIP 協(xié)議的優(yōu)缺點(diǎn) RIP 協(xié)議最大的優(yōu)點(diǎn)就是實(shí)現(xiàn)簡(jiǎn)單，開(kāi)銷較小。缺點(diǎn)：RIP 限制了網(wǎng)絡(luò)的規(guī)模，它能使用的最大距離為 15（16 表示不可達(dá)）。路由器之間交換的路由信息是路由器中的完整路由表，因而隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，開(kāi)銷也就增加。“壞消息傳播的慢”，使更新過(guò)程的收斂

54、時(shí)間過(guò)長(zhǎng)。當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí)，要經(jīng)過(guò)比較長(zhǎng)的時(shí)間才能將此信息傳送到所有的路由器。8、鏈路狀態(tài)路由控制OSPF 協(xié)議即開(kāi)放最短路徑優(yōu)先。OSPF最主要的特征就是使用分步式的鏈路狀態(tài)路由選擇算法，三個(gè)要點(diǎn)：（1）向本自治系統(tǒng)中所有路由器發(fā)送信息，這就是路由器通過(guò)所有輸出端口向它所有相鄰的路由器發(fā)送信息。而每一個(gè)相鄰路由器又再將此信息發(fā)往其所有的相鄰路由器(但不再發(fā)送給剛剛發(fā)來(lái)信息的那個(gè)路由器)。這樣，最終整個(gè)區(qū)域中所有的路由器都得到這個(gè)信息的一個(gè)副本。（2）發(fā)送的信息就是與本路由器相鄰的所有路由器的鏈路狀態(tài)，但這只是路由器所知道的部分信息。所謂“鏈路狀態(tài)”就是說(shuō)明本路由器都和哪些路由器相鄰，以及該鏈

55、路的“度量”。（3）只有當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)，路由器才用洪泛法向所有路由器發(fā)送此信息。OSPF的其他特點(diǎn)：OSPF對(duì)不同的鏈路可根據(jù) IP 分組的不同服務(wù)類型 TOS 而設(shè)置成不同的代價(jià)。因此，OSPF 對(duì)于不同類型的業(yè)務(wù)可計(jì)算出不同的路由。如果到同一個(gè)目的網(wǎng)絡(luò)有多條相同代價(jià)的路徑，那么可以將通信量分配給這幾條路徑。這叫作多路徑間的負(fù)載平衡。所有在 OSPF 路由器之間交換的分組都具有鑒別的功能。支持可變長(zhǎng)度的子網(wǎng)劃分和無(wú)分類編址 CIDR。每一個(gè)鏈路狀態(tài)都帶上一個(gè)32位的序號(hào)，序號(hào)越大狀態(tài)就越新。OSPF 還規(guī)定每隔一段時(shí)間，如30分鐘，要刷新一次數(shù)據(jù)庫(kù)中的鏈路狀態(tài)。 由于一個(gè)路由器的鏈路狀

56、態(tài)只涉及到與相鄰路由器的連通狀態(tài)，因而與整個(gè)互聯(lián)網(wǎng)的規(guī)模并無(wú)直接關(guān)系。因此當(dāng)互聯(lián)網(wǎng)規(guī)模很大時(shí)，OSPF協(xié)議要比距離向量協(xié)議 RIP 好得多。 OSPF 沒(méi)有“壞消息傳播得慢”的問(wèn)題，其響應(yīng)網(wǎng)絡(luò)變化的時(shí)間小于100 ms。 鏈路狀態(tài)路由：鏈路狀態(tài)路由算法中，每個(gè)節(jié)點(diǎn)將它所知的路由信息傳達(dá)給其鄰近節(jié)點(diǎn)。首先，一個(gè)節(jié)點(diǎn)收集與鄰節(jié)點(diǎn)相連的每條鏈路的狀態(tài)信息。例如，鏈路的比特率、通過(guò)鏈路發(fā)送報(bào)文的延遲時(shí)間、緩沖區(qū)中報(bào)文的數(shù)目以及鏈路的可靠性等等，諸如此類的信息。這些都是決定鏈路費(fèi)用的因素。其次，節(jié)點(diǎn)為每個(gè)連接建立一個(gè)鏈路狀態(tài)報(bào)文。這類報(bào)文指出通過(guò)那條鏈路相連的兩個(gè)節(jié)點(diǎn)和它收集的鏈路信息。然后節(jié)點(diǎn)將報(bào)文發(fā)

57、送給每個(gè)鄰節(jié)點(diǎn)。再者，收到鏈路狀態(tài)報(bào)文的節(jié)點(diǎn)將它轉(zhuǎn)發(fā)給所有的其它鄰近節(jié)點(diǎn)。最后，由于鏈路狀態(tài)報(bào)文在節(jié)點(diǎn)間交換，最終，每個(gè)節(jié)點(diǎn)都可以知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及網(wǎng)絡(luò)節(jié)點(diǎn)間的鏈路狀態(tài)和費(fèi)用。只要每個(gè)節(jié)點(diǎn)定期地建立并發(fā)送包含當(dāng)前信息的鏈路狀態(tài)報(bào)文，這種方法就能對(duì)網(wǎng)絡(luò)費(fèi)用的增長(zhǎng)和下降作出響應(yīng)。它還能對(duì)鏈路失效作出反應(yīng)。此外，如果一條鏈路失效，所有的節(jié)點(diǎn)能通過(guò)鏈路狀態(tài)報(bào)文最終了解這一情況。因此，它們可以確定新路徑來(lái)避開(kāi)無(wú)效鏈路。9、Patricia路由表查找Patricia前綴樹(shù)(Patricia Trie)PATRICIA算法被廣泛應(yīng)用在信息檢索系統(tǒng)中，檢索信息時(shí)是逐比特(或字符)進(jìn)行的，樹(shù)的所有數(shù)據(jù)信息都

58、存放在葉子PATRICIAtrie消除了所有的單分支節(jié)點(diǎn),所有非葉子節(jié)點(diǎn)的分支都為2,PATRICIAtrie是深度最淺的trie。PATRICIAtrie通過(guò)消除單分支中間節(jié)點(diǎn)大大壓縮了trie的深度,壓縮搜索路徑能夠減少搜索時(shí)間1PATRICIA算法在許多領(lǐng)域都得到了廣泛的應(yīng)用。PATRICIA算法非常適合狀態(tài)表操作,主要因?yàn)镻ATRICIAtrie是深度最淺的trie;支持定長(zhǎng)匹配;算法的時(shí)間性能與數(shù)據(jù)寬度無(wú)關(guān),非常適合數(shù)據(jù)寬度很大的情況;。10、DTMF信號(hào)的帶內(nèi)和帶外傳送方法雙音多頻信號(hào)（DTMF）雙音多頻，由高頻群和低頻群組成，高低頻群各包含4個(gè)頻率。一個(gè)高頻信號(hào)和一個(gè)低頻信號(hào)疊加組成一個(gè)組合信號(hào)，代表一個(gè)數(shù)字。DTMF信號(hào)有16個(gè)編碼。利用DTMF信令可選擇呼叫相應(yīng)的對(duì)講機(jī)。即撥號(hào)音。，電話系統(tǒng)中電話機(jī)與交換機(jī)之間的一種用戶信令