建設網(wǎng)站以什么為導向濟南全網(wǎng)推廣
目錄
一、網(wǎng)絡鏈路
二、廣播信道要解決問題
三、多路訪問協(xié)議
1、基本介紹
2、多路訪問協(xié)議的類型(3)
四、信道劃分協(xié)議
1、時分多路訪問 TDMA
2、頻分多路訪問 FDMA
3、碼分多路訪問 CDMA(略)
五、隨機訪問協(xié)議
1、純 ALOHA
2、時隙 ALOHA
3、CSMA 載波偵聽多路訪問
4、CSMA/CD 帶沖突檢測的
六、輪流協(xié)議
1、輪詢(polling)
2、令牌傳遞(token passing)
一、網(wǎng)絡鏈路
兩種網(wǎng)絡鏈路:
- 點對點鏈路:鏈路兩端各一個節(jié)點,一個發(fā)送和一個接收。
- 廣播鏈路:多個發(fā)送節(jié)點和接收節(jié)點連接到一個共享的廣播信道。
廣播:當任何一個節(jié)點傳輸一幀時,信號在信道上廣播,其它節(jié)點都可以收到一個拷貝。
廣播常用于局域網(wǎng) LAN 中,如早期的以太網(wǎng)和無線局域網(wǎng),即以太網(wǎng)和無線局域網(wǎng)使用的是廣播鏈路層技術(shù)。本節(jié)主要學習廣播鏈路的信道共享技術(shù)。
二、廣播信道要解決問題
① 傳統(tǒng)的廣播電視:是單向的廣播,一個固定的節(jié)點向許多接收節(jié)點發(fā)送。
② 計算機網(wǎng)絡:廣播信道上的所有節(jié)點都能夠發(fā)送和接收。
- 類似于許多人聚集在一起交談,此時空氣是廣播信道;
- 解決 “誰在什么時候獲得說話權(quán)力” 問題,即誰有權(quán)向信道發(fā)送。
③ 多路訪問問題:如何協(xié)調(diào)多個發(fā)送節(jié)點和接收節(jié)點對共享廣播信道的訪問。
④ 多路訪問協(xié)議:用于解決多路訪問問題的相關(guān)技術(shù)。
三、多路訪問協(xié)議
1、基本介紹
① 目的:協(xié)調(diào)多個節(jié)點在共享廣播信道上的傳輸。
避免多個節(jié)點同時使用信道,發(fā)生沖突,從而產(chǎn)生互相干擾。
② 沖突(collide):兩個或兩個以上的節(jié)點同時傳輸幀,使接收方收不到正確的幀。
所有沖突的幀都因受損而被丟失,從而造成廣播信道時間的浪費。
③ 多路訪問協(xié)議可以用于許多不同的網(wǎng)絡環(huán)境,如有線和無線局域網(wǎng)、衛(wèi)星網(wǎng)等。
④ 理想的多址訪問協(xié)議:對于一個速率為 R bps 的廣播信道,
- 當一個節(jié)點有數(shù)據(jù)發(fā)送時,它能以 R bps 的速率發(fā)送;
- 當有 M 個節(jié)點要發(fā)送數(shù)據(jù),每個節(jié)點的平均發(fā)送速率為 R/M bps;
- 完全分散:不需要一個主節(jié)點來協(xié)調(diào)傳輸;不需要時鐘、時隙同步
- 簡單
需要時鐘、時隙同步指的是將在后面介紹的時隙 ALOHA 。ALOHA 協(xié)議和 CSMA 協(xié)議只有第一個特性,而沒有第二個特性。
2、多路訪問協(xié)議的類型(3)
?
① 信道劃分協(xié)議
- 把信道劃分為小片,即時隙
- 給每個節(jié)點分配專用的小片
② 隨機訪問協(xié)議
- 不劃分信道,允許產(chǎn)生沖突
- 但是必須能夠從沖突中恢復
③ 輪流協(xié)議
- 通過輪流訪問信道的方式避免沖突
- 要發(fā)送的節(jié)點越多輪流的時間越長
四、信道劃分協(xié)議
主要有TDMA、FDMA、CDMA三種。
設信道支持 N 個節(jié)點,傳輸速率是 R b/s。
1、時分多路訪問 TDMA
time division multiple access
TDMA:將時間劃分為時間幀(time frame),每個時間幀再劃分為 N 個時隙(slot),時隙的長度保證能發(fā)送一個分組,分別分配給 N 個節(jié)點。每個節(jié)點只能在固定分配的時隙中傳輸。
這里的分組就是指的鏈路層的幀!原書為了避免將其和時間幀混淆,所以改叫分組。
例:具有 6 個節(jié)點的 LAN,時隙 1、3、4? 有分組,時隙 2、5、6 空閑。
TDMA 的特點
- 避免了沖突、公平:每個節(jié)點專用速率 R/N bps;
- 節(jié)點速率有限:R/N bps;
- 效率不高:節(jié)點必須等待它的傳輸時隙;
- 資源浪費:信道可能處于空閑狀態(tài)。
2、頻分多路訪問 FDMA
frequency division multiple access
FDMA:將總信道帶寬 R bps 劃分為 N 個較小信道,即劃分為 N 個帶寬為 R/N 的頻段,分別分配給 N 個節(jié)點。
例:具有 6 個節(jié)點的 LAN,頻段 1、3、4? 有分組,頻段 2、5、6 空閑。
FDMA 特點
- 避免了沖突、公平:每個節(jié)點專用速率 R/N bps;
- 節(jié)點帶寬有限、效率不高:節(jié)點帶寬為 R/N bps。
3、碼分多路訪問 CDMA(略)
frequency division multiple access
- 每個節(jié)點分配一個唯一的編碼
- 每個節(jié)點用它唯一的編碼來對它發(fā)送的數(shù)據(jù)進行編碼
- 允許多個節(jié)點共存,信號可疊加,即可以同時傳輸數(shù)據(jù)而無沖突
如果編碼是正交化的,則可以同時傳輸數(shù)據(jù)而無沖突。
五、隨機訪問協(xié)議
基本思想:
- 發(fā)送節(jié)點以信道的全部速率 R bps 發(fā)送;
- 發(fā)生沖突時,沖突中的每個節(jié)點分別等待一個隨機時間;
- 等待一個隨機時間后再重發(fā),直到幀/分組發(fā)送成功;
- 節(jié)點間沒有協(xié)調(diào)者。
典型隨機訪問協(xié)議:
- ALOHA 協(xié)議(純 ALOHA、時隙 ALOHA)
- 載波監(jiān)聽多路訪問協(xié)議 CSMA
- 帶沖突檢測的載波監(jiān)聽多路訪問協(xié)議 CSMA/CD
- 帶沖突避免的載波監(jiān)聽多路訪問協(xié)議 CSMA/CA
1、純 ALOHA
又稱非時隙 ALOHA,實現(xiàn)簡單,不需要時隙同步。
基本操作:幀一旦到達,節(jié)點立即進行傳輸。
沖突處理:如果與其它幀產(chǎn)生沖突,則在該沖突幀傳完之后以概率 p 立即重傳該幀;或等待一個幀的傳輸時間,再以概率 p 傳輸該幀,或者以概率 1-p 等待另一個幀的時間。
rand(0, 1); // 規(guī)定隨機數(shù)大于p則不傳,否則則傳
以概率 p 立即重傳就是等待一個隨機時間,在計算機中實現(xiàn)就是產(chǎn)生一個隨機數(shù),若該隨機數(shù)大于某值則繼續(xù)產(chǎn)生隨機數(shù),否則立即重傳。
沖突概率
為什么這里鏈路層的幀都是一樣長?因為假設了所有幀大小相同。
2、時隙 ALOHA
做出以下假設:
- 所有幀大小相同
- 時間被劃分為相同大小的時隙,一個時隙等于傳送一幀的時間
- 節(jié)點只在一個時隙的開始傳輸幀
- 節(jié)點是同步的,每個節(jié)點都知道時隙何時開始
- 所有節(jié)點都能在時隙結(jié)束之前檢測到?jīng)_突
時隙 ALOHA 的實現(xiàn)
當節(jié)點要發(fā)送新幀時,它需要等到下一時隙開始時才能傳送,
- 如果沒有沖突,則節(jié)點可以在下一時隙開始時發(fā)送新幀;
- 如果有沖突,則節(jié)點在隨后的時隙以概率 p 重傳該幀,直到成功為止。
時隙 ALOHA 的優(yōu)點
- 單個活躍節(jié)點可以持續(xù)以滿速率傳送幀
- 具有高分散性:只需節(jié)點的時隙同步
- 實現(xiàn)簡單
時隙 ALOHA 的缺點
- 因為允許沖突,所以會浪費時隙
- 存在空閑時隙
- 節(jié)點只有在傳輸數(shù)據(jù)包時才能檢測到?jīng)_突
?
時隙 ALOHA 的效率
- 效率:是指當有很多節(jié)點,且每個節(jié)點有很多幀要發(fā)送時,成功時隙所占百分比。
- 最佳情況:信道有 37% 的有效傳輸。
3、CSMA 載波偵聽多路訪問
載波偵聽:某個節(jié)點在發(fā)送之前,先監(jiān)聽信道。
- 信道忙:該節(jié)點隨機等待/回退一段時間,然后再偵聽信道。
- 信道空:該節(jié)點開始傳輸整個數(shù)據(jù)幀。
人類類比:在自己說話之前,先聽一下有沒有其他人正在說話,不要打斷他人說話!
CSMA 的特點:
- 節(jié)點在發(fā)送之前進行監(jiān)聽,可以減少沖突。
- 由于存在傳播時延,因此仍有可能出現(xiàn)沖突,從而造成信道浪費。
傳播時延:信號從一個節(jié)點傳播到另一個節(jié)點所花費的時間。該傳播時延越長,載波偵聽節(jié)點不能偵聽到網(wǎng)絡中另一個節(jié)點已經(jīng)開始傳輸?shù)臋C會就越大。
CSMA 發(fā)送沖突舉例
請忽略圖中左側(cè)文字,這是后面 CSMA/CD 的功能。
帶來問題:信道浪費。
注意:距離與傳播時延對碰撞概率的影響。
節(jié)點沒有進行沖突檢測,即使發(fā)生了沖突,節(jié)點仍繼續(xù)傳輸它們的幀。但該幀已經(jīng)被破壞,是無用的幀,因此信道傳輸時間被浪費。
4、CSMA/CD 帶沖突檢測的
具有 “載波偵聽” 和 “沖突檢測” 這兩個功能。
載波偵聽:傳送前偵聽
- 信道忙:延遲傳送
- 信道閑:傳送整個幀
沖突檢測:發(fā)送的過程中一旦檢測到?jīng)_突就立即停止傳輸,盡快重發(fā)。
- 目的:縮短無效傳送時間,提高信道的利用率。
以太網(wǎng) CSMA/CD 的運行機制
① 適配器從網(wǎng)絡層得到分組,創(chuàng)建鏈路層幀。
② 適配器進行載波偵聽:
- 信道閑,則開始傳送幀。
- 信道忙,則等到信道閑時再傳送幀。
③ 當信道閑時適配器開始傳送幀:
- 若適配器在整個發(fā)送中都沒有檢測到其它傳送,則完成該幀的傳送。
- 若適配器在發(fā)送中檢測到其它傳送,則放棄傳送并發(fā)送一個擁塞信號。
前者已經(jīng)不需要接收方回復確認信息了,因為適配器一直在偵聽,并且沒有發(fā)現(xiàn)沖突。?
⑤ 適配器放棄傳送后進入 指數(shù)回退階段:
注意選擇范圍是連續(xù)的一串整數(shù),中間沒有跳過任何一個整數(shù)。
以太網(wǎng) CSMA/CD 的運行機制討論
擁塞信號:長為 48 比特,確保所有傳送者知道沖突發(fā)生。
比特時間:是指發(fā)送 1 比特所用的時間。
- 對于 10 Mbps Ethernet 為 0.1 微秒
- 當 K=1023 時,等待時間大約為 52 毫秒
指數(shù)回退算法
目標:適配器依據(jù)當前負載情況重傳,負載越重等待時間越長。
- 第一次沖突: 在 {0, 1} 中選 K 值,延遲 Kx512 比特時間傳送;
- 第二次沖突: 在 {0, 1, 2, 3} 中選 K 值,延遲 Kx512 比特時間傳送;
- 10 次以后,在 {0, 1, 2, 3, 4, …, 1023} 中選 K 值;
- 沖突超過 16 次,則放棄重傳!
K 值是等概率選擇的。
六、輪流協(xié)議
1、輪詢(polling)
輪詢解決了沖突和時隙空閑的問題。
?
主節(jié)點邀請從節(jié)點依次傳送:
由主節(jié)點通知從節(jié)點?“它可以傳輸” ,并且規(guī)定了每個從節(jié)點每次能發(fā)送的時間。
主節(jié)點采用輪詢的方式,依次給各個從節(jié)點分配時間,保證了一個節(jié)點開始發(fā)送后不會再有其它節(jié)點開始發(fā)送。該從節(jié)點發(fā)送完畢后將會通知主節(jié)點,主節(jié)點再去輪詢,去給下一個需要發(fā)送的從節(jié)點分配時間。
輪詢 1:你要發(fā)嗎?我要發(fā)。那好你發(fā)吧,但只能發(fā) xx 時間哦,發(fā)完了告訴我。我發(fā)完了。
輪詢 2:你要發(fā)嗎?我暫時不發(fā)。
輪詢 3:你要發(fā)嗎?我要發(fā)。那好你發(fā)吧,但只能發(fā) xx 時間哦,發(fā)完了告訴我。我發(fā)完了。
輪詢的問題:
- 輪詢的開銷:通知一個節(jié)點 “它可以傳輸” 所需的時間
- 單點故障:一旦主節(jié)點寄了,其它從節(jié)點都因為沒有通知而沒辦法發(fā)
2、令牌傳遞(token passing)
控制令牌按順序從一個節(jié)點傳遞到下一個節(jié)點,并且規(guī)定只能持有令牌 xx 時間。令牌和幀都采用同方向且單方向傳輸,因為如果數(shù)據(jù)采用雙向傳輸,那么它自己都會和自己產(chǎn)生沖突。
PC1 發(fā)送完畢將令牌傳遞給 PC2,PC2 因為不需要發(fā)送,所以直接把令牌傳遞給 PC3,PC3 拿到令牌后開始發(fā)送幀。
令牌傳遞的問題:
- 令牌開銷:令牌就是數(shù)據(jù)
- 單點失效(token):令牌出錯則視為丟失,誰都發(fā)不了
假設令牌持有時間為 2 秒,則上圖 PC 最多等待 6 秒。若等待時間大于 6 秒,則發(fā)現(xiàn)令牌丟失,從而 PC 們會爭相產(chǎn)生新的令牌。