第12章_多路訪問

1、幾個要點幾個要點隨機訪問隨機訪問(Random Access)/競爭競爭(Contention): 各站點平等各站點平等,沒有任何站點能控制其他站點沒有任何站點能控制其他站點;只要遵循預只要遵循預定義的程序定義的程序,包括介質(zhì)狀態(tài)的檢測包括介質(zhì)狀態(tài)的檢測,滿足條件的每一個站點都滿足條件的每一個站點都能傳輸數(shù)據(jù)。能傳輸數(shù)據(jù)。兩個特點：兩個特點：1.每一個站點的傳輸每一個站點的傳輸隨機性隨機性2.為了訪問介質(zhì)，各站點采用為了訪問介質(zhì)，各站點采用“競爭競爭”機制機制 在隨機訪問中，各站點都有權訪問介質(zhì)且不受控于其他在隨機訪問中，各站點都有權訪問介質(zhì)且不受控于其他站點，而如果有超過一個站點都在發(fā)送數(shù)據(jù)

2、時，就產(chǎn)生了站點，而如果有超過一個站點都在發(fā)送數(shù)據(jù)時，就產(chǎn)生了“沖突沖突”（Collision）要解決的幾個關鍵問題要解決的幾個關鍵問題1.站點何時能訪問介質(zhì)站點何時能訪問介質(zhì)2.如果介質(zhì)忙，站點要怎么做如果介質(zhì)忙，站點要怎么做3.各站點如何確定其數(shù)據(jù)傳輸是否成功各站點如何確定其數(shù)據(jù)傳輸是否成功4.如果發(fā)生沖突，應如何解決如果發(fā)生沖突，應如何解決lCSMA/CD及其早先的技術可以叫做“隨機訪問”或“爭用”技術。l之所以說是“隨機訪問”，是指沒有為每個站點的發(fā)送規(guī)定某個可預計或有計劃的時間，站點發(fā)送的順序是隨機的。l之所以說是“爭用”，是指站點需要爭奪線路的時間來獲得發(fā)送權。l這些技術中最早的是

3、ALOHA協(xié)議. ALOHA：夏威夷人傳統(tǒng)問候語或分別時用語夏威夷人傳統(tǒng)問候語或分別時用語lAloha協(xié)議或稱Aloha技術、Aloha網(wǎng)，是世界上最早的無線電計算機通信網(wǎng)。l它是1968年美國夏威夷大學的一項研究計劃的名字，由該大學的Abramson等人 于70年代初研制成功的一種使用無線廣播技術的分組交換計算機網(wǎng)絡，也是世界上最早、最基本的無線數(shù)據(jù)通信協(xié)議。l這項研究計劃的目的是要解決夏威夷群島之間的通信問題。Aloha網(wǎng)絡可以使分散在各島的多個用戶通過無線電信道來使用中心計算機，從而實現(xiàn)一點到多點的數(shù)據(jù)通信。 Aloha協(xié)議或Aloha網(wǎng)，是世界上最早的無線電計算機通信網(wǎng)。它是1968年

4、美國夏威夷大學的一項研究計劃的名字。70年代初研制成功一種使用無線廣播技術的分組交換計算機網(wǎng)絡，也是最早最基本的無線數(shù)據(jù)通信協(xié)議。取名Aloha，是夏威夷人表示致意的問候語，這項研究計劃的目的是要解決夏威夷群島之間的通信問題。Aloha網(wǎng)絡可以使分散在各島的多個用網(wǎng)絡可以使分散在各島的多個用戶通過無線電信道來使用中心計算機，戶通過無線電信道來使用中心計算機，從而實現(xiàn)一點到多點的數(shù)據(jù)通信。從而實現(xiàn)一點到多點的數(shù)據(jù)通信。 發(fā)送l網(wǎng)上各站點在任何時刻只要需要，就可以自由地發(fā)送信息（以幀的形式）。l信息發(fā)送完畢，發(fā)送站等待一段時間，等待時間等于信道上最遠的兩個站之間的傳輸時延的兩倍。l若在等待時間內(nèi)收

5、到接收站的確認信息，則表明發(fā)送成功，否則重發(fā)該數(shù)據(jù)幀。但為了避免繼續(xù)沖突，各站需等待一段隨機時間后再重發(fā)；若再產(chǎn)生沖突，則再等待一段隨機時間再重發(fā)l若多次重發(fā)都失?。ㄈ允詹坏酱_認信息），則停止發(fā)送該幀。ALOHAALOHA協(xié)議的最大特點是協(xié)議的最大特點是“想說就說想說就說”。接收l接收站根據(jù)“幀校驗字段”（同HDLC幀）值對所接收的幀進行差錯檢驗。l如果檢驗無差錯，而且地址相符，接收站就發(fā)送一個確認幀。否則就丟棄所接收的幀。l幀可能因信道噪聲或同一時間其他站點傳輸發(fā)出的幀而損壞 (發(fā)生沖突了)。任何幀相遇都會立即產(chǎn)生沖突（collision）l純ALOHA協(xié)議最大的缺點是最大吞吐率不到理想值的

6、18.4% (吞吐率：成功發(fā)送的信息數(shù)與實際發(fā)送的信息數(shù)之比)。lALOHA的改進版，1972年由Robert提出，可將吞吐率提高一倍。l將信道時間分為等長的時間長度,每個長度正好等于一個幀的傳輸時間（又稱“時隙”或“分槽“ Slot）。l所有站點的時鐘必須保持同步。l各站只能在時隙的起始時間才能開始發(fā)送信息。 這樣只有那些都在同一個時隙開始進行傳輸?shù)膸庞锌赡軟_突。l故此可能發(fā)生沖突的危險區(qū)比ALOHA降低了大約一半，在任一幀傳輸時無其他幀發(fā)送的概率約為0.368，即信道的吞吐率最大可達37%。l純ALOHA和時隙ALOHA的傳輸效率都不高，主要原因是各站獨立地決定發(fā)送的時刻,使得沖突的概率

7、很高,信道利用率下降。lCSMA要求各站在發(fā)送之前先監(jiān)聽信道上是否有其他站點正在傳送（載波監(jiān)聽）。如果有，就稍候；如果無，就發(fā)送。l如果多個站點同時發(fā)送，就會產(chǎn)生沖突，導致信息混淆，傳輸失敗。l站點在傳輸后將等待一定時間（往返時間加上確認幀爭用時間）以接收確認幀。收不到確認(因沖突)就重傳。l最大吞吐率遠遠超過純ALOHA和時隙ALOHA，取決于傳播時間（媒體長度）和幀的長度：幀越長，傳播時間越短，吞吐率越高。l使用CSMA，需要某種算法來規(guī)定發(fā)現(xiàn)信道忙時各站點應該采取的策略。l于是就有了幾種采用不同載波監(jiān)聽策略的CSMA技術：l非堅持CSMAl1-堅持CSMAlP-堅持CSMAl性能: CS

8、MA 時隙 ALOHA 純 ALOHAl如果信道忙，等待一個隨機時間，然后再次對信道進行監(jiān)聽。l如果信道空閑，剛立即發(fā)送。l等待一個隨機時間，然后重新開始。l如果信道忙，繼續(xù)監(jiān)聽信道，一旦發(fā)現(xiàn)信道空閑，立即發(fā)送。l等待一個隨機時間，然后重新開始。l之所以稱為“1-堅持”，原因是主機一發(fā)現(xiàn)信道空閑，百分之百（即概率為1）肯定發(fā)送。l如果信道忙，等待直到信道空閑。l信道空閑，可能發(fā)送(概率為P) ，可能延遲一個時間單位再發(fā)送 (概率為1-P)。時間單位通常等于最大傳播時延。l等待一個隨機時間，然后重新開始。每個站在發(fā)送數(shù)據(jù)前，先監(jiān)聽信道上有無其他站正在發(fā)送信息，若無，則發(fā)送數(shù)據(jù)；則有，則暫不發(fā)送，

9、退避一段時間后再嘗試。其最大的特點是“先聽后說先聽后說”。CSMA的監(jiān)聽策略有三種算法： 非堅持非堅持 一旦監(jiān)聽到信道忙就不再堅持聽下去，延遲一段隨機時間后再重新監(jiān)聽。（信道利用率不高）1-堅持堅持 監(jiān)聽到信道忙時仍然堅持聽下去，直到空閑為止。一旦信道空閑就發(fā)送。如有沖突，等待一隨機時間后再監(jiān)聽。（沖突較大）P-堅持堅持 監(jiān)聽到信道忙時仍然堅持聽下去，直到空閑為止。當聽到信道空閑時，以概率p發(fā)送數(shù)據(jù)。(p=1時，即為1堅持） p-堅持的主要問題是如何確定一個合適的p 值。l輕載時，1堅持CSMA吞吐量特性最好；l重載時，非堅持CSMA吞吐量特性最好，但時間延遲增大。l以太網(wǎng)是典型的采用竟爭方式

10、解決介質(zhì)占用問題的局域網(wǎng)技術，它的介質(zhì)訪問規(guī)則有三個關鍵點：1.連接在介質(zhì)上的多個節(jié)點對介質(zhì)擁有同等的訪問權限。采用競爭的方式來決定某一時刻由哪個節(jié)點來占用介質(zhì)，同一時刻內(nèi)可能有多個節(jié)點訪問網(wǎng)絡，這就是所謂的“多路訪問”。2.節(jié)點判斷網(wǎng)絡介質(zhì)是否空閑以及發(fā)送是否成功都是通過載波監(jiān)聽的方式來實現(xiàn)的。3.從1、2兩點來看，以太網(wǎng)不可能避免兩個節(jié)點同時發(fā)送數(shù)據(jù)的情況出現(xiàn)，這就會產(chǎn)生沖突，因此必須設法避免沖突造成的不可恢復的通信差錯，這就要進行沖突檢測。l介質(zhì)訪問規(guī)則：l如何控制節(jié)點訪問網(wǎng)絡介質(zhì)l由MAC層定義lCSMA/CD：Carrier-Sense Multiple Access with Co

11、llision Detection，帶沖突檢測的載波偵聽和多路訪問l工作過程：l先聽后發(fā)先聽后發(fā)l邊聽邊發(fā)邊聽邊發(fā)l沖突回退沖突回退l候時重發(fā)候時重發(fā)l比喻：一個文雅的座談會l l 當一個站點想要發(fā)送數(shù)據(jù)的時候，它檢測網(wǎng)絡查看是否當一個站點想要發(fā)送數(shù)據(jù)的時候，它檢測網(wǎng)絡查看是否有其他站點正在傳輸，即監(jiān)聽信道是否空閑。有其他站點正在傳輸，即監(jiān)聽信道是否空閑。l如果信道忙，則等待，直到信道空閑。如果信道忙，則等待，直到信道空閑。l l 如果信道閑，站點就傳輸數(shù)據(jù)。如果信道閑，站點就傳輸數(shù)據(jù)。l l 在發(fā)送數(shù)據(jù)的同時，站點繼續(xù)監(jiān)聽網(wǎng)絡確信沒有其他站在發(fā)送數(shù)據(jù)的同時，站點繼續(xù)監(jiān)聽網(wǎng)絡確信沒有其他站點在

12、同時傳輸數(shù)據(jù)。因為有可能兩個或多個站點都同時檢點在同時傳輸數(shù)據(jù)。因為有可能兩個或多個站點都同時檢測到網(wǎng)絡空閑然后幾乎在同一時刻開始傳輸數(shù)據(jù)。如果兩測到網(wǎng)絡空閑然后幾乎在同一時刻開始傳輸數(shù)據(jù)。如果兩個或多個站點同時發(fā)送數(shù)據(jù)，就會產(chǎn)生沖突。個或多個站點同時發(fā)送數(shù)據(jù)，就會產(chǎn)生沖突。l l 當一個傳輸結(jié)點識別出一個沖突，它就發(fā)送一個擁塞信當一個傳輸結(jié)點識別出一個沖突，它就發(fā)送一個擁塞信號，這個信號使得沖突的時間足夠長，讓其他的結(jié)點都有號，這個信號使得沖突的時間足夠長，讓其他的結(jié)點都有能發(fā)現(xiàn)。能發(fā)現(xiàn)。l l 其他結(jié)點收到擁塞信號后，都停止傳輸，等待一個隨機其他結(jié)點收到擁塞信號后，都停止傳輸，等待一個隨機

13、產(chǎn)生的時間間隙（回退時間，產(chǎn)生的時間間隙（回退時間，Backoff Time）后重發(fā)。）后重發(fā)。CSMA/CD的工作原理四句話具體過程如下：的工作原理四句話具體過程如下：開始檢測介質(zhì)（監(jiān)聽）介質(zhì)忙？發(fā)送幀碰撞？隨機退避時間YESNONOYES繼續(xù)發(fā)送直至完成整體效能30%50%安全區(qū)域注意區(qū)域危險區(qū)域網(wǎng)絡繁忙時間：使用設備數(shù)量21030PCDesktop publishingwith laser printerDiskless CAD/CAMworkstation整體效能l總線型和星型拓撲的網(wǎng)絡最常用的媒體訪問控制技術是CSMA/CD(載波監(jiān)聽多路訪問)協(xié)議。l以太網(wǎng)是使用IEEE 802.3

14、標準（即采用CSMA/CD訪問控制技術）的網(wǎng)絡系統(tǒng)。l以太網(wǎng)是最流行的局域網(wǎng)系統(tǒng)。由于以太網(wǎng)與其他LAN類型相比，具有易用、易安裝、易維護、低成本等諸多優(yōu)點，目前世界上8085%與LAN相連的PC和工作站使用以太網(wǎng)連接。l載波監(jiān)聽載波監(jiān)聽l目的：降低沖突次數(shù)l如果信道空閑，立即發(fā)送l如果信道忙，等待直到信道空閑l沖突檢測沖突檢測l目的：降低沖突的影響，使信道在沖突發(fā)生可以盡快恢復使用l一檢測到?jīng)_突就放棄傳輸，等待一個隨機時間，然后重新監(jiān)聽。l每站在發(fā)送數(shù)據(jù)前，先監(jiān)聽信道是否空閑；若是，則發(fā)送數(shù)據(jù)，并繼續(xù)監(jiān)聽下去，一旦監(jiān)聽到?jīng)_突，立即停止發(fā)送，并在短時間內(nèi)連續(xù)向信道發(fā)出一串阻塞信號（JAM）強化

15、沖突，如果信道忙，則暫不發(fā)送，退避一隨機時間后再嘗試。lCSMA/CD協(xié)議在CSMA協(xié)議基礎上增加了發(fā)送期間檢測沖突的功能。其最大特點是“”。該協(xié)議已被IEEE 802委員會采納，并以此為依據(jù)制定了IEEE 802.3標準。lCSMA/CD協(xié)議同樣可分為“非堅持” 、“1-堅持” 和“p-堅持” 三種。l以太網(wǎng)通常采用非時隙1-堅持CSMA/CD。l一個站點有數(shù)據(jù)要發(fā)送時，要先將其沖突計數(shù)器清零，然后監(jiān)聽電纜，看是否有其他站點的載波(信號)在傳送。l“監(jiān)聽”可以通過監(jiān)測電纜上是否有電流（每個比特大致為 1820 毫安）來實現(xiàn)。每個比特是以10 MHz (快速以太網(wǎng)為100 MHz）的時鐘頻率進

16、行曼徹斯特編碼后發(fā)送的。l如果信道沒有空閑，就等待，直到信道空閑。然后還要再等一個小的“幀間隔”（IFG）時間（最小為9.6微秒）以便讓所有接收站點有時間為下一輪的傳輸作好準備。 【幀間隔幀間隔】以太網(wǎng)數(shù)據(jù)幀之間的最小時間間隔，用于設備恢復，以便下一幀數(shù)據(jù)的接收。任何一個以太網(wǎng)幀，則在傳輸前都要等待一個幀間隔時間。只有此期間網(wǎng)絡持續(xù)空閑，才能開始試發(fā)送。幀間隔使網(wǎng)路上的各個設備都有相同的機會獲得發(fā)送權。lCSMA并不能避免兩個站點同時發(fā)送。如果兩個站點都想發(fā)送，而且都監(jiān)聽到信道是空閑的，它們將都認定目前無人在使用信道。這樣就會產(chǎn)生沖突。l每個正在發(fā)送數(shù)據(jù)的站點都繼續(xù)監(jiān)聽自己的發(fā)送過程。如果發(fā)現(xiàn)

17、沖突（如同軸電纜上的電流值超過24毫安），就立即停止發(fā)送，而改發(fā)一個32比特的阻塞碼。發(fā)送阻塞碼的目的是確保各接收方將因CRC差錯而丟棄該幀。l帶沖突檢測的監(jiān)聽算法把浪費帶寬的時間減少到檢測沖突的時間。l為保證在幀傳輸時間內(nèi)能檢測到?jīng)_突，要求限制最小幀長(持續(xù)時間應不小于2倍的最大傳播時延)。接收站將對小于最小幀長的幀當作沖突碎片處理而丟棄之。l如果只有一個站點要發(fā)送，該站點可占用整個傳輸信道，所以可獲得將近100%的信道利用率。l即在一個10 Mbps 的網(wǎng)絡上可獲得將近10 Mbps 的吞吐量。l如果有兩個或更多個站點要同時發(fā)送，線路利用率和吞吐率就會下降部分帶寬被沖突和退避延遲消耗了。l

18、實際上，一條共享10 Mbps 以太網(wǎng)絡通常只能提供24 Mbps的吞吐量給所連接的各個站點。l隨著網(wǎng)絡利用率的增加，特別是如果有許多站點爭用時,可能出現(xiàn)過載情況。此時，網(wǎng)絡的吞吐量將急劇下降，信道容量的大部分被CSMA/CD算法耗費掉，只有極小部分用于傳送有用的數(shù)據(jù)。為什么一個共享的以太網(wǎng)要求站點數(shù)不得超過1024個，原因就在此。l許多工程師以利用率達到40%作為LAN過載的臨界值。利用率較高的LAN將出現(xiàn)高沖突率，傳輸時間也極可能變化很大（由于退避）。l使用網(wǎng)橋或交換機將LAN分成兩個或更多個沖突域?qū)⑹菢O其有益的。l為了確保所有站點都能在發(fā)送站完成發(fā)送前開始接收到幀，以太網(wǎng)規(guī)定了最小幀長（

19、如要求每個幀有效長度不小于64個字節(jié)）。最小幀長與網(wǎng)絡跨距、所用的傳輸媒體類型以及信號達到LAN的最遠端時需要通過的中繼器的數(shù)目有關。l所有這些因素定義了一個稱為“以太網(wǎng)時隙”的參數(shù)。帶寬為10 Mbps 或 100 Mbps的以太網(wǎng)時隙為512比特（64字節(jié)，對10 Mbps以太網(wǎng)為51.2微秒）時間，帶寬為 1000 Mbps的以太網(wǎng)時隙為4096比特（512字節(jié)）時間。l在一個繁忙的網(wǎng)絡上，如果所有站點在沖突發(fā)生后都試圖立即重發(fā)，肯定會引起所謂“二次沖突”。所以，要求采取措施將同時重發(fā)的概率降低到最小。以太網(wǎng)技術使用的是所謂“隨機退避時間”，即每個站點選擇一個隨機數(shù)，乘以時隙時間（即最小

20、幀長時間51.2 微秒）。規(guī)定重發(fā)前必須先等這一個隨機時間。l退避算法中還規(guī)定須對重發(fā)次數(shù)（N）進行計數(shù)，并將最大重發(fā)次數(shù)限定為16次，即16次沖突后站點將放棄發(fā)送，并報告一個錯誤。l每次重發(fā)時,發(fā)送站點先構造一個數(shù)列: 0, 1, 2, 3, 4, 5, . L ，其中L為2K -1，K=N，K10。然后從該數(shù)列中隨機取一個數(shù)R。發(fā)送站點退避等待（延遲發(fā)送）時間為Rx時隙時間，即 R x 51.2 微秒（對10Mbps以太網(wǎng)）。l當網(wǎng)絡中出現(xiàn)沖突時，發(fā)生沖突的發(fā)送站點將延遲（退避）一個時間（由退避算法決定）后才能重發(fā)。退避算法要求每個發(fā)送站點在試圖重新傳輸前必須等待的時間應為時隙（51.2

21、微秒）的整數(shù)倍。該整數(shù)的取值則由下式?jīng)Q定： 0 R 2 K -1，式中 K = min (N, 10)l變量K實際上是沖突的次數(shù)，只是最大值為10。所以，R的范圍是0至1023（K=10時）。R的實際取值是由每個以太網(wǎng)站點的隨機程序決定的。隨著連續(xù)沖突次數(shù)的增加，可能產(chǎn)生的退避時間范圍將呈指數(shù)增加。l規(guī)定最大重發(fā)次數(shù)不超過16次。l在兩次沖突之后, N=2，于是K=2，數(shù)列范圍為 0, 1, 2, 3 ，表明再次沖突的概率為四分之一。對應的等待時間則為 0, 51.2, 102.4, 153.6 微秒中的一個。l在三次沖突之后，N = 3，數(shù)列范圍為 0, 1, 2, 3, 4, 5, 6, 7，表明再次沖突的概率為八分之一。l而在四次沖突之后，N=4，數(shù)列