目錄

一、網(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 的廣播信道，

1. 當一個節(jié)點有數(shù)據(jù)發(fā)送時，它能以 R bps 的速率發(fā)送；
2. 當有 M 個節(jié)點要發(fā)送數(shù)據(jù)，每個節(jié)點的平均發(fā)送速率為 R/M bps；
3. 完全分散：不需要一個主節(jié)點來協(xié)調(diào)傳輸；不需要時鐘、時隙同步
4. 簡單

需要時鐘、時隙同步指的是將在后面介紹的時隙 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é)議：

1. ALOHA 協(xié)議（純 ALOHA、時隙 ALOHA）
2. 載波監(jiān)聽多路訪問協(xié)議 CSMA
3. 帶沖突檢測的載波監(jiān)聽多路訪問協(xié)議 CSMA/CD
4. 帶沖突避免的載波監(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)生新的令牌。