通信網(wǎng)理論基礎整理

1、基本概念基本概念1、REDRED：提前隨機丟棄：提前隨機丟棄(Rom(RomEarlyEarlyDetection)Detection)；擁塞控制；擁塞控制是一種主動隊列管理算法。Rom:指按照一定的概率丟棄；Early:發(fā)生在隊列已滿之前；detection:只是為分組標記，更傾向于被丟棄。通過監(jiān)控路由器輸出端口隊列的平均長度來探測擁塞，一旦發(fā)現(xiàn)擁塞逼近，即平均隊列長度超過一個閾值，就以一定的概率丟包或者在分組上作標記來通知相應的連接

2、來減小發(fā)送速率，使他們在隊列溢出導致丟包之前減小擁塞窗口，降低發(fā)送數(shù)據(jù)速度，從而緩解網(wǎng)絡擁塞，也就是說在緩沖區(qū)滿之前就按照一定的比例（即丟棄概率）隨機地將緩沖區(qū)的數(shù)據(jù)丟棄或標記。隨機早期檢測（RED，RomEarlyDetection）算法將隊列的平均隊長作為決定擁塞避免機制是否應被處罰的隨機函數(shù)的參數(shù)，增加了在隊列長度變得太大之前平滑瞬時擁塞的可能性，可以過濾掉短期隊長的變化，減少了同時使多個流受分組丟棄影響的可能性，使得因特網(wǎng)數(shù)據(jù)突

3、發(fā)本質(zhì)或短暫擁塞不會平均使隊長有明顯變化。概率與長度問題計算：（1）若平均隊列長度小于最小門限，則把新到達的分組放入隊列進行排隊（p=0）；（2）若平均minTH隊列長度超過最大門限，則把新到達的分組丟棄（分組丟棄概率p=1）；（3）若平均隊列長度在最小門限和最大門限maxTHminTH之間，則按照某一概率p（01）將新到達的分組丟棄。RED不是等到已經(jīng)發(fā)生網(wǎng)絡擁塞后才把所有在隊列尾部的分組全部丟棄，maxTH而是在檢測到網(wǎng)絡擁塞的早期

4、征兆時（即路由器的平均隊列長度超過一定的門限值時），就以概率p隨機丟棄個別的分組，讓擁塞控制只在個別的TCP連接上進行，因而避免發(fā)生全局性的擁塞控制。平均隊列長度（）)()()1(當前的隊列長度樣本舊的???????AVAVLL)10(???)()(minmaxminmaxTHTHTHLppavtemp????（count代表新到達的分組有多少個已經(jīng)進入隊列）。)1(temptemppcountpp???AQM:主動隊列管理（Activ

5、equeuemanagement）主動而非相應性的分組丟棄，提早通知發(fā)送方降低速率。包含有REDSREDFRED等。另一種擁塞控制：tail：尾部丟棄（被動），隊列達到最大長度，通過丟包來指示擁塞，告知發(fā)送方調(diào)整發(fā)送速率。2、GBNGBNARQ:ARQ:返回返回N自動請求重發(fā)（自動請求重發(fā)（GoGobackbackNautomaticautomaticrepeatrepeatreQuestreQuest）；差錯控制；差錯控制發(fā)送方在沒有

6、收到對方應答的情況下，可以持續(xù)的發(fā)送多個幀（窗口大?。?，假如發(fā)現(xiàn)已發(fā)送的第N幀中有錯誤發(fā)生，那么回退到第N幀及其之后所有的幀全部再重新發(fā)送，窗口越大重傳幀數(shù)越多，而上述過程可以自動完成，不需要上層干預。最大窗口值：21（i為比特數(shù)）ARQ其他類型：停等式(stopwait）ARQ（在開始下一幀傳送之前，必須確保當前幀已被正確接收），選擇性重傳（iverepeat）ARQ（發(fā)送端不用等待接收端的應答，持續(xù)發(fā)送多幀，假如發(fā)現(xiàn)已發(fā)送的幀中有錯

7、誤，只重新發(fā)送那個發(fā)生錯誤的幀）。3、BEBBEB：二進制指數(shù)退避（：二進制指數(shù)退避（binarybinaryexponentialexponentialbackoffbackoff）：流量控制：流量控制依據(jù)通信環(huán)境的變化，自適應調(diào)整沖突窗口時間值，提供了一個處理重負荷的方法。具體是指：一旦檢測到?jīng)_突，為降低再沖突的概率，需要等待一個隨機時間，然后再使用CSMA方法試圖傳輸。為了保證這種退避維持穩(wěn)定，采用了二進制指數(shù)退避算法的技術(shù)。遇到

8、重復的沖突時，站點將重復傳輸，但在每一次沖突之后，通信窗口的時間t隨n翻倍，從而減小發(fā)生沖突的概率，這是一種自適應算法。嘗試傳輸?shù)闹貜褪е赂L的退避時間，這將有助于負荷的平滑。具體實現(xiàn)：?具體的退避算法如下:（1）確定基本退避時間，它就是爭用期（以太網(wǎng)的端到端往返時間，以太網(wǎng)把爭用期定為?251.2）；（2）從離散的整數(shù)集合(k為重傳次數(shù))中隨機取出一個數(shù)，記為r。重傳應推后的時間就是r倍的爭用期。s?]12..10[?k(3)當重

9、傳16次仍不能成功時（這表明同時打算發(fā)送數(shù)據(jù)的站太多，以致連續(xù)發(fā)生沖突），則丟棄該幀，并向]10min[重傳次數(shù)，?k高層報告。?PPT：（1）準備就緒時，在（0，w1）一致性隨機選擇延后發(fā)送；（2）起始時，最大不超過；minCWw?maxCW（3）沖突發(fā)生后，w倍增；（4）如遇信道忙，w凍結(jié)。所謂截斷就是有一個上限，不能無限制的加倍。4、LPMLPM：最長前綴匹配（：最長前綴匹配（longestlongestprefixprefixm

10、atchmatch）；路由表查找；路由表查找最長前綴匹配是指在IP協(xié)議中路由器用于在路由表中進行選擇的一個算法。Prefix:前綴，即IP地址中的前綴部分，對用于網(wǎng)絡號。在使用CIDR時，由于采用了網(wǎng)絡前綴這種記法，IP地址由網(wǎng)絡前綴和主機號這兩個部分組成，這時，路由表中的每個項目由“網(wǎng)絡前綴”和“下一跳地址”組成。但是在查找路由表時可能會得到不止一個匹配結(jié)果。應當從匹配結(jié)果中選擇具有最長網(wǎng)絡前綴的路由。這是因為網(wǎng)絡前綴越長，其地址塊就

11、越小，因而路由就越具體。在CIDR中，路由表中的每個表項都指定了一個網(wǎng)絡，可能存在多行路由表記錄能匹配同一個IP地址，找出前綴長度最長的匹配項，即子網(wǎng)掩碼最長的一個作為匹配依據(jù)。IP路由器查找轉(zhuǎn)發(fā)表或路由表：IP前綴與出口之間的映射關(guān)系。適用于單播路由：分組只有一個目標地址；路由器查表，得到匹配項最長前綴的表項及出口；關(guān)鍵問題:快速查找。5、CSMA:CSMA:載波偵聽多址接入（載波偵聽多址接入（carriercarriersenses

12、ensemultiplemultipleaccessaccess）；多用戶接入所謂載波偵聽，意思是網(wǎng)絡上各個工作站在發(fā)送數(shù)據(jù)前都要偵聽總線上有沒有數(shù)據(jù)傳輸。若有數(shù)據(jù)傳輸，則不發(fā)送數(shù)據(jù)；若無數(shù)據(jù)傳輸，立即發(fā)送準備好的數(shù)據(jù)。CSMA是從ALOHA協(xié)議演變出的一種改進型協(xié)議，它采用了附加的硬件裝置，每個節(jié)點都能夠檢測（偵聽）到信道上有無分組在傳輸。如果一個節(jié)點有分組要傳輸，它首先檢測信道是否空閑，如果信道有其他分組在傳輸，則該節(jié)點可以等到信道

13、空閑后再傳輸，這樣可以減少要發(fā)送的分組與正在傳輸?shù)姆纸M之間的碰撞，提高系統(tǒng)的利用率?！岸帱c接入”就是說明這是總線型網(wǎng)絡，許多計算機以多點接入的方式連接在一根總線上，且發(fā)送數(shù)據(jù)是廣播式的。6、BHCABHCA：忙時呼叫量（：忙時呼叫量（busybusyhourhourcallcallattemptattempt）；業(yè)務度量；業(yè)務度量是通信業(yè)務工程中用于測量、評估和規(guī)劃電話網(wǎng)絡呼叫處理能力的一個關(guān)鍵性指標。BHCA是指在一天中一個通信系統(tǒng)最

14、繁忙的一個小時（高峰時期一般為早上9點到10點）電話呼叫的請求總次數(shù)。單位：次小時.單位時間系統(tǒng)用于呼叫的開銷：t=abn(a固有開銷；b處理一次呼叫的平均開銷，N即BHCA)。7、ESRESR：誤碼秒率或誤碼秒百分數(shù)（：誤碼秒率或誤碼秒百分數(shù)（ErredErredSecondSecondRatioRatio）：服務質(zhì)量指標：服務質(zhì)量指標(以秒為單位以秒為單位)隙。每一個用戶所占用的時隙是周期性地出現(xiàn)（其周期就是TDM幀的長度），時分復

15、用的所有用戶是在不同的時間占用同樣的頻帶寬度。（2）STDM是一種改進的時分復用，它能明顯地提高信道的利用率。STDM使用STDM幀來傳送復用的數(shù)據(jù)。但每一個STDM幀中的時隙數(shù)小于連接在集中器上的用戶數(shù)。各用戶有了數(shù)據(jù)就隨時發(fā)往集中器的輸入緩存，然后集中器按順序依次掃描輸入緩存，把緩存中的輸入數(shù)據(jù)放入STDM幀中。對沒有數(shù)據(jù)的緩存就跳過去。當一個幀的數(shù)據(jù)放滿了，就發(fā)送出去。因此，STDM幀不是固定分配時隙，而是按需動態(tài)地分配時隙。因此

16、統(tǒng)計時分復用可以提高線路的利用率。使用統(tǒng)計時分復用的集中器也叫做智能復用器，它能提供對整個報文的存儲轉(zhuǎn)發(fā)能力，通過排隊方式使各用戶更合理地共享信道。所有用戶在統(tǒng)計上是時分復用的。與TDM幾乎無關(guān)，TDM是分配給該用戶的時隙，永遠被占用（獨享），只是STDM從統(tǒng)計上來說是時分復用的。1414、TCPTCP：傳輸控制協(xié)議（：傳輸控制協(xié)議（TransmissionTransmissionControlControlProtocolProtoc

17、ol）：端到端傳輸復用：端到端傳輸復用TCP是一種面向連接的、可靠的、基于字節(jié)流的傳輸層通信協(xié)議，由IETF的RFC793定義。在簡化的計算機網(wǎng)絡OSI模型中，它完成第四層傳輸層所指定的功能。在因特網(wǎng)協(xié)議族（Interprotocolsuite）中，TCP層是位于IP層之上，應用層之下的中間層。不同主機的應用層之間經(jīng)常需要可靠的、像管道一樣的連接，但是IP層不提供這樣的流機制，而是提供不可靠的包交換。應用層向TCP層發(fā)送用于網(wǎng)間傳輸?shù)摹?/p>

18、用8位字節(jié)表示的數(shù)據(jù)流，然后TCP把數(shù)據(jù)流分區(qū)成適當長度的報文段。之后TCP把結(jié)果包傳給IP層，由它來通過網(wǎng)絡將包傳送給接收端實體的TCP層。TCP為了保證不發(fā)生丟包，就給每個包一個序號，同時序號也保證了傳送到接收端實體的包的按序接收。然后接收端實體對已成功收到的包發(fā)回一個相應的確認（ACK）；如果發(fā)送端實體在合理的往返時延（RTT）內(nèi)未收到確認，那么對應的數(shù)據(jù)包就被假設為已丟失將會被進行重傳。TCP用一個校驗和函數(shù)來檢驗數(shù)據(jù)是否有錯誤

19、；在發(fā)送和接收時都要計算校驗和。TCPTCP三次握手的過程如下：三次握手的過程如下：客戶端發(fā)送SYN（SEQ=x）報文給服務器端，進入SYN_SEND狀態(tài)；服務器端收到SYN報文，回應一個SYN（SEQ=y）ACK(ACK=x1）報文，進入SYN_RECV狀態(tài)；客戶端收到服務器端的SYN報文，回應一個ACK(ACK=y1）報文，進入Established狀態(tài)。三次握手完成，TCP客戶端和服務器端成功地建立連接，可以開始傳輸數(shù)據(jù)了。TCP

20、最主要的特點：（1）TCP是面向連接的運輸層協(xié)議。這就是說，應用程序在使用TCP協(xié)議之前，必須先建立TCP連接。在傳送數(shù)據(jù)完畢后，必須釋放已經(jīng)建立的TCP連接；（2）每一條TCP連接只能有兩個端點，每一條TCP連接只能是點對點的（一對一）；（3）TCP提供可靠交付的服務。也就是說，通過TCP連接傳送的數(shù)據(jù)，無差錯、不丟失、不重復、并且按序到達。（4）TCP提供全雙工通信。TCP允許通信雙方的應用進程在任何時候都能發(fā)送數(shù)據(jù)。（5）面向字節(jié)

21、流。1515、CACCAC：呼叫接納控制（：呼叫接納控制（CallCallAdmissionAdmissionControlControl）；流量工程；流量工程CAC：是通過限制進入網(wǎng)絡的呼叫連接數(shù)量來降低網(wǎng)絡擁塞概率和呼叫中斷概率的方法。其目的是維護網(wǎng)絡的穩(wěn)定性、保證無線鏈路質(zhì)量和合理利用系統(tǒng)容量。其一般性原理如下：即系統(tǒng)必須有足夠的資源支持呼叫用戶的請求，并且新用戶的加入不能影響己經(jīng)存在的用戶的QoS。相關(guān)文獻提出的呼叫接納控制的標

22、準為：系統(tǒng)預先估計新呼叫接納后的用戶QoS，而當所有用戶的QoS都達到要求時，呼叫才能被接納。若不能容納新的呼叫則拒絕。呼叫接納控制已廣泛應用于許多通信網(wǎng)中，如ATM通信網(wǎng)和移動蜂窩系統(tǒng)。僅對VoIP的業(yè)務流，不影響普通數(shù)據(jù)業(yè)務的技術(shù)；對實時性或時延敏感的業(yè)務，依據(jù)網(wǎng)絡負載情況，決定呼叫接續(xù)與否，是保證服務質(zhì)量的一項技術(shù)。CAC方法：本地決策（依據(jù)歷史經(jīng)驗，設置固定的允許呼叫的上限）；基于測量的決策（發(fā)啟方通過測量到達目標節(jié)點的丟失率和

23、延時，決定呼叫的接續(xù)與否）；基于資源的決策（計算所需與可用的資源，或者執(zhí)行資源預留操作，再決定呼叫的接續(xù)）。1616、DFSDFS：深度優(yōu)化查找（：深度優(yōu)化查找（DepthfirstsearchDepthfirstsearch）；單播路由算法它是搜索算法的一種，目的是要達到被搜索結(jié)構(gòu)的葉節(jié)點。對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次。步驟如下：（1）當節(jié)點V的所有關(guān)聯(lián)邊都已被探尋過時，搜索將回溯到發(fā)現(xiàn)節(jié)點V的

24、父節(jié)點，這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止；（2）否則選擇V的關(guān)聯(lián)邊e，到下一點y：如果y已查過，則e為回退邊；如果y未查過，e為樹邊，以y替代x重復第1步。每次深度優(yōu)先搜索的結(jié)果必然是圖的一個連通分量。深度優(yōu)先搜索可以從多點發(fā)起。如果將每個節(jié)點在深度優(yōu)先搜索過程中的“結(jié)束時間”排序(具體做法是創(chuàng)建一個list然后在每個節(jié)點的相鄰節(jié)點都已被訪問的情況下，將該節(jié)點加入list結(jié)尾，然后逆轉(zhuǎn)整個鏈表)則我們可以得到所謂的“拓

25、撲排序”，即topologicalst.(搜索原理：在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續(xù)漢下去。當節(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復以上過程，整個進程反復進行直到所有節(jié)點都被訪問為止。屬于盲目搜索。其過程簡要來說是對每一個可能的分支路徑深入到不能

26、再深入為止而且每個節(jié)點只能訪問一次。深度優(yōu)先搜索所遵循的搜索策略是盡可能“深“地搜索圖。)（2）BFS（BreadthFirstSearch）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，

27、直到找到結(jié)果為止。BFS并不使用經(jīng)驗法則算法。從算法的觀點，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中。一般的實驗里，其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為open的容器中（例如隊列或是鏈表），而被檢驗過的節(jié)點則被放置在被稱為closed的容器中。1717、MSTMST：最小生成樹（：最小生成樹（MinimumMinimumSpanningSpanningTreeTree）；多播路由算法對于一個無向連通圖G=