計算機網(wǎng)絡(luò)（網(wǎng)絡(luò)學(xué)院） 第四章 局域網(wǎng)與介質(zhì)訪問子層

1、計算機網(wǎng)絡(luò)局域網(wǎng)與介質(zhì)訪問子層（基本概念）第四章局域網(wǎng)與介質(zhì)訪問子層局域網(wǎng)概述局域網(wǎng)拓撲結(jié)構(gòu)和傳輸介質(zhì)信道分配多路訪問協(xié)議局域網(wǎng)的IEEE 802系列標(biāo)準(zhǔn)網(wǎng)橋技術(shù)2概念局域網(wǎng)常覆蓋一棟大樓或一組建筑群，網(wǎng)上最遠網(wǎng)點間數(shù)據(jù)傳輸距離不超過一、兩公里。廣義上講，局域網(wǎng)以外的網(wǎng)絡(luò)都可以歸入“廣域網(wǎng)”的范疇。但是，在實踐中也有人在局域網(wǎng)與廣義的“廣域網(wǎng)”之間引入了園區(qū)網(wǎng)和城域網(wǎng)的概念。從本質(zhì)上講，園區(qū)網(wǎng)主要是由局域網(wǎng)互連而成，因此，以局域網(wǎng)技術(shù)為主；而城域網(wǎng)跨度較大，需要采用遠程通信技術(shù)，即廣域網(wǎng)技術(shù)，實際上是廣域網(wǎng)與局域網(wǎng)技術(shù)的結(jié)合。局域網(wǎng)產(chǎn)生的原因80年代，微型機發(fā)展迅速，彼此需要相互通信（近距離）

2、，共享資源；功能分布：分布式計算，分布式數(shù)據(jù)庫3基本屬性定義局域網(wǎng)是一種將小區(qū)域內(nèi)的各種通信設(shè)備互連在一起的通信網(wǎng)絡(luò)。局域網(wǎng)的三個屬性局域網(wǎng)是一種通信網(wǎng)絡(luò)通信設(shè)備是廣義的在一個小區(qū)域內(nèi)4局域網(wǎng)基本特點局域網(wǎng)的重要特點之一是網(wǎng)絡(luò)吞吐率高，通常以Mbps為單位。目前的局域網(wǎng)技術(shù)中以10 Mbps、100 Mbps和155 Mbps為典型單網(wǎng)數(shù)據(jù)吞吐率指標(biāo)。高吞吐率決定了局域網(wǎng)技術(shù)不能實用傳統(tǒng)的電話線路，而必須使用專用通信介質(zhì)，如同軸電纜、光纜或優(yōu)質(zhì)雙絞線。使用專用電纜或光纜的場合，由于成本較高，通常采用共享通信介質(zhì)的方式，多臺計算機掛在同一段通信介質(zhì)上。為了保證共享通信介質(zhì)的多臺機器能分時交換信息

3、，局域網(wǎng)必須具備控制使用通信介質(zhì)的機制，即介質(zhì)訪問控制MAC（Medium Access Control）。盡管介質(zhì)訪問控制增加了訪問控制的難度，但共享介質(zhì)方式的附加優(yōu)點是有利于實現(xiàn)網(wǎng)上廣播和組地址訪問功能。5局域網(wǎng)拓撲結(jié)構(gòu)和傳輸介質(zhì)局域網(wǎng)拓撲結(jié)構(gòu)星型結(jié)構(gòu)環(huán)型結(jié)構(gòu)總線型結(jié)構(gòu)樹型結(jié)構(gòu)傳輸介質(zhì)雙絞線基帶同軸電纜光纖無線6使用星型網(wǎng)絡(luò)拓撲結(jié)構(gòu)需要每一臺計算機使用電纜連接到Hub上；在一個星型的網(wǎng)絡(luò)中可能會有很多連接到Hub的電纜線。7Caption: A Proxim RangeLAN wireless local area network interface card. Also shown is

4、 a table-top antenna which attaches to the interface card. 8Caption: An AirLAN wireless local area network interface card. The white rectangular object is a wall or ceiling mount antenna which attaches to the interface. 9Caption: A RangeLAN wireless local area network PCMCIA interface card. The blac

5、k object attached to the left of the card is its antenna. 10Caption: A RangeLAN wireless PCMCIA network interface card. Attached is its wireless tranceiver and antenna. 11信道分配計算機網(wǎng)絡(luò)可以分成兩類使用點到點連接的網(wǎng)絡(luò) 廣域網(wǎng)使用廣播信道（多路訪問信道，隨機訪問信道）的網(wǎng)絡(luò)局域網(wǎng)關(guān)鍵問題：如何解決對信道爭用解決信道爭用的協(xié)議稱為介質(zhì)訪問控制協(xié)議 MAC（Medium Access Control），是數(shù)據(jù)鏈路層協(xié)議的一部分

6、。12信道分配方法靜態(tài)分配頻分多路復(fù)用 FDM（波分復(fù)用WDM）原理：將頻帶平均分配給每個要參與通信的用戶；優(yōu)點：適合于用戶較少，數(shù)目基本固定，各用戶的通信量都較大的情況；缺點：無法靈活地適應(yīng)站點數(shù)及其通信量的變化。時分多路復(fù)用 TDM原理：每個用戶擁有固定的信道傳送時槽；優(yōu)點：適合于用戶較少，數(shù)目基本固定，各用戶的通信量都較大的情況；缺點：無法靈活地適應(yīng)站點數(shù)及其通信量的變化。13靜態(tài)FDM性能分析設(shè)信道容量為C bps，信道數(shù)據(jù)到達率為幀/秒，每幀的長度服從指數(shù)概率密度函數(shù)分布，其平均值為1/比特/幀，則平均延時T為：假如把單個信道分配為N個獨立的子信道，那么每個子信道的容量應(yīng)為C/N b

7、ps。每個子信道的平均數(shù)據(jù)到達率為/N，重新計算T，則：14信道分配方法動態(tài)分配信道分配模型的五個基本假設(shè)：站點模型：每個站點是獨立的，并以統(tǒng)計固定的速率產(chǎn)生幀，一幀產(chǎn)生后到被發(fā)送走之前，站點被封鎖；單信道假設(shè)：所有的通信都是通過單一的信道來完成的，各個站點都可以從信道上收發(fā)信息；沖突假設(shè)：若兩幀同時發(fā)出，會相互重疊，結(jié)果使信號無法辨認，稱為沖突。所有的站點都能檢測到?jīng)_突，沖突幀必須重發(fā)；連續(xù)時間和時間分槽（確定何時發(fā)送）；載波監(jiān)聽和非載波監(jiān)聽（確定能否發(fā)送）。15多路訪問協(xié)議定義：控制多個用戶共用一條信道的協(xié)議ALOHA協(xié)議70年代，Norman Abramson設(shè)計了ALOHA協(xié)議目的：解

8、決信道的動態(tài)分配，基本思想可用于任何無協(xié)調(diào)關(guān)系的用戶爭用單一共享信道使用權(quán)的系統(tǒng)；分類：純ALOHA協(xié)議和分槽ALOHA協(xié)議純ALOHA協(xié)議基本思想：用戶有數(shù)據(jù)要發(fā)送時，可以直接發(fā)至信道；然后監(jiān)聽信道看是否產(chǎn)生沖突，若產(chǎn)生沖突，則等待一段隨機的時間重發(fā);16在純ALOHA中，完全任意地發(fā)送幀17ALOHA協(xié)議的效率競爭系統(tǒng)：多用戶共享單一信道，并由此產(chǎn)生沖突，這樣的系統(tǒng)稱為競爭系統(tǒng)；信道效率假設(shè)：幀長固定，無限個用戶，按泊松分布產(chǎn)生新幀，平均每個幀時（frame time）產(chǎn)生S幀（0 S 1）；發(fā)生沖突重傳，新舊幀共傳k次，遵從泊松分布，平均每個幀時產(chǎn)生G幀；吞吐率 S = GP0，P0為發(fā)

9、送一幀不受沖突影響的概率；沖突危險區(qū)一個幀時內(nèi)產(chǎn)生k幀的概率：Prk = ，兩個幀時平均產(chǎn)生2G個幀，在沖突危險區(qū)內(nèi)無其它幀產(chǎn)生的概率為：P0 = e-2G，所以 S = Ge-2G；效率：信道利用率最高只有18.4%.18陰影幀的沖突危險區(qū)19 ALOHA系統(tǒng)中吞吐率和幀產(chǎn)生率之間的關(guān)系20分槽ALOHA協(xié)議基本思想：把信道時間分成離散的時間槽，槽長為一個幀所需的發(fā)送時間。每個站點只能在時槽開始時才允許發(fā)送。其他過程與純ALOHA協(xié)議相同。信道效率沖突危險區(qū)是純ALOHA的一半，所以P0 = e-G，S = Ge-G；與純ALOHA協(xié)議相比，降低了產(chǎn)生沖突的概率，信道利用率最高為36.8%。

10、21載波監(jiān)聽多路訪問協(xié)議CSMA （Carrier Sense Multiple Access Protocols）載波監(jiān)聽（Carrier Sense）站點在為發(fā)送幀而訪問傳輸信道之前，首先監(jiān)聽信道有無載波，若有載波，說明已有用戶在使用信道，則不發(fā)送幀以避免沖突。多路訪問（Multiple Access）多個用戶共用一條線路1-堅持型CSMA（1-persistent CSMA）原理若站點有數(shù)據(jù)發(fā)送，先監(jiān)聽信道；若站點發(fā)現(xiàn)信道空閑，則發(fā)送；若信道忙，則繼續(xù)監(jiān)聽直至發(fā)現(xiàn)信道空閑，然后完成發(fā)送；若產(chǎn)生沖突，等待一隨機時間，然后重新開始發(fā)送過程。22優(yōu)點：減少了信道空閑時間；缺點：增加了發(fā)生沖突的

11、概率；廣播延遲對協(xié)議性能的影響：廣播延遲越大，發(fā)生沖突的可能性越大，協(xié)議性能越差；非堅持型CSMA（nonpersistent CSMA）原理若站點有數(shù)據(jù)發(fā)送，先監(jiān)聽信道；若站點發(fā)現(xiàn)信道空閑，則發(fā)送；若信道忙，等待一隨機時間，然后重新開始發(fā)送過程；若產(chǎn)生沖突，等待一隨機時間，然后重新開始發(fā)送過程。優(yōu)點：減少了沖突的概率；缺點：增加了信道空閑時間，數(shù)據(jù)發(fā)送延遲增大；信道效率比 1-堅持CSMA高，傳輸延遲比 1-堅持CSMA大。23p-堅持型CSMA（p-persistent CSMA）適用于分槽信道原理若站點有數(shù)據(jù)發(fā)送，先監(jiān)聽信道；若站點發(fā)現(xiàn)信道空閑，則以概率p發(fā)送數(shù)據(jù)，以概率q =1- p

12、延遲至下一個時槽發(fā)送。若下一個時槽仍空閑，重復(fù)此過程，直至數(shù)據(jù)發(fā)出或時槽被其他站點所占用；若信道忙，則等待下一個時槽，重新開始發(fā)送；若產(chǎn)生沖突，等待一隨機時間，然后重新開始發(fā)送。24各種隨機訪問協(xié)議的信道利用和載荷曲線的比較五種多路訪問協(xié)議性能比較25帶沖突檢測的載波監(jiān)聽多路訪問協(xié)議CSMA/CD引入原因當(dāng)兩個幀發(fā)生沖突時，兩個被損壞幀繼續(xù)傳送毫無意義，而且信道無法被其他站點使用，對于有限的信道來講，這是很大的浪費。如果站點邊發(fā)送邊監(jiān)聽，并在監(jiān)聽到?jīng)_突之后立即停止發(fā)送，可以提高信道的利用率，因此產(chǎn)生了CSMA/CD原理站點使用CSMA協(xié)議進行數(shù)據(jù)發(fā)送；在發(fā)送期間如果檢測到?jīng)_突，立即終止發(fā)送，并

13、發(fā)出一個瞬間干擾信號，使所有的站點都知道發(fā)生了沖突；在發(fā)出干擾信號后，等待一段隨機時間，再重復(fù)上述過程。26工作狀態(tài)傳輸周期競爭周期空閑周期27問題一個站點確定發(fā)生沖突要花多少時間？最壞情況下，2倍電纜傳輸時間假設(shè)信號在兩個相距最遠的站點間傳輸?shù)臅r間為。在t0時刻，一個站點開始發(fā)送，經(jīng)過-之后，即在信號到達最遠的那個站點之前，最遠的站點也開始發(fā)送。當(dāng)然最遠端的站點幾乎立即就會檢測到?jīng)_突而取消發(fā)送，但是由沖突產(chǎn)生的一點點突發(fā)噪聲必須經(jīng)過2-長的時間后才能反饋到初發(fā)站。28無沖突協(xié)議（Collision-Free Protocols）基本位圖協(xié)議（A Bit-Map Protocol）工作原理共享

14、信道上有N個站，競爭周期分為N個時槽，如果一個站有幀發(fā)送，則在對應(yīng)的時槽內(nèi)發(fā)送比特1；N個時槽之后，每個站都知道哪個站要發(fā)送幀，這時按站序號發(fā)送。29特點象這樣在實際發(fā)送信息前先廣播發(fā)送請求的協(xié)議稱為預(yù)留協(xié)議（reservation protocol）效率輕負載下，效率為 d / (N + d)，數(shù)據(jù)幀由d個時間單位組成；重負載下，效率為 d / (d + 1)。缺點與站序號有關(guān)的不平等性，序號大的站得到的服務(wù)好；每個站都有 1 比特的開銷。30二進制倒計數(shù)數(shù)法（Binary Countdown）工作原理所有站的地址用等長二進制位串表示，若要占用信道，則廣播該位串；不同站發(fā)的地址中的位做“或”

15、操作，一旦某站了解到比本站地址高位更高的位置被置為“1”，便放棄發(fā)送請求。效率d / (d + log2N)31二進制倒計數(shù)法的改進采用并行接口，而不是串行接口建議使用虛擬站號，每次傳輸之后，對站重新編號，從0開始，已成功傳送的站排在最后，這樣長時間沉默的站點將會獲得較高的優(yōu)先權(quán)。32有限競爭協(xié)議（Limited-Contention Protocols）占用信道的策略競爭方法例，CSMA；輕負載下，發(fā)送延遲?。恢刎撦d下，信道效率低。無沖突方法例，基本位圖法；輕負載下，發(fā)送延遲大；重負載下，信道效率高。有限競爭方法結(jié)合以上兩種方法，輕負載下使用競爭，重負載下使用無沖突方法。下圖：減少競爭的站的

16、數(shù)目可以增加獲取信道的概率；基本思路：將站分組，組內(nèi)競爭；問題：如何分組？33對稱協(xié)議的性能假設(shè)共有k個站點參與信道競爭，每個站點在每個時隙內(nèi)的發(fā)送概率為 p，那么在某一給定時隙內(nèi)站點成功獲取信道的概率為kp(1-p)k-1。當(dāng)p=1/k時，Pr取最大值。34對稱競爭信道獲取概率35分組的討論（1）每個組只有一個成員（2）每個組擁有兩個成員（3）一個組包含所有成員找到一種動態(tài)分組的方法，在輕載荷時每個組多分一些站點，在重載荷時，每個組少分一些站點。36適應(yīng)樹搜索協(xié)議（The Adaptive Tree Walk Protocol）工作原理站點組織成二叉樹；一次成功傳輸之后，第0時隙全部站可競爭

17、信道，只有一個站要使用信道則發(fā)送；有沖突則在第1槽內(nèi)半數(shù)站（2以下站）參與競爭。如其中之一獲得信道，本幀后的時槽留給3以下的站；如發(fā)生沖突，繼續(xù)折半搜索。當(dāng)系統(tǒng)負載很重時，從根結(jié)點開始競爭發(fā)生沖突的概率非常大。為提高效率，可以從中間結(jié)點開始競爭。問題：搜索應(yīng)該從樹的哪一級開始？37例1一組N站點共享一個56kbps的純ALOHA信道。每個站點平均每100秒輸出一個1000bit的幀，即使前一個幀還沒有發(fā)送完也依舊進行（例如，站點都有緩存）。N的最大值是多少？解答：對于ALOHA協(xié)議，最大可用的帶寬是：56kbps*0.184=10.304kbps每個站點需要的帶寬為：1000/100=10bp

18、s所以N=10304/10=103038例2一萬個航空定票站在競爭使用單個分槽ALOHA通道。各站平均每小時做18次請求，一個槽是125s，總的通道負載有多少？解答：各站每小時18次，一萬個站，所以一秒鐘有180000/3600=50個請求，一個槽是125s，一秒鐘有8000個槽。所以平均每個時槽發(fā)送次數(shù)為：50/8000=1/160?？偟耐ǖ镭撦dG=1/160.39例3廣播子網(wǎng)的一個缺點是有多個主機試圖訪問信道時造成的信道容量浪費。作為一個簡單的例子，假設(shè)把時間分為離散的時間片，n臺主機中每一臺主機在每個時間片內(nèi)試圖占有信道的概率為p。求由于沖突被浪費的時間片的比例。解答：所有主機都不占有信

19、道的概率為： （1-p)n只有一個主機試圖占有信道的概率為：np(1-p)n-1所以由于沖突被浪費的時間片的比例為： 1-np(1-p)n-1-(1-p)n40例4一個局域網(wǎng)采用Mok和Ward版本的二進制倒記數(shù)法。在某一時刻，10個站點的虛站號為8,2,4,5,1,7,3,6,9,0. 要發(fā)送的下3個站點是上述序列中的4,3,9。當(dāng)3個站點全部完成發(fā)送后，新的虛站號是什么？解答：發(fā)送序號為4的站點后的新虛站號為： 8 3 0 5 2 7 4 6 9 1 發(fā)送原序號為3的站點后的新虛站號為： 8 4 1 5 3 7 0 6 9 2 發(fā)送原序號為9的站點后的新虛站號為： 9 5 2 6 4 8 1 7 0 341例516個站點正在競爭一條采用自適應(yīng)樹遍歷協(xié)議的共享信道。如果地址編號為素數(shù)的站點突然全部準(zhǔn)備發(fā)送，那么需要多少個時槽才能解決競爭？解答：共需13個時槽；第一個時槽： 2 3 5 7 11 13 第二個時槽