1、1,4.3 隨機(jī)接入技術(shù): ALOHA(Additive Link On-line HAwaii System),目標(biāo)：當(dāng)網(wǎng)絡(luò)的通信量較小時(shí)，讓用戶(hù)自由地發(fā)送數(shù)據(jù)所產(chǎn)生沖突的概率并不大，只要協(xié)議考慮到如何處理好沖突的問(wèn)題。像這樣的多點(diǎn)接入方式稱(chēng)為隨機(jī)接入。 純ALOHA ALOHA網(wǎng)絡(luò)是美國(guó)Hawaii大學(xué)于1968年9月研制，于1970年建立的分組傳送的由無(wú)線電信道組成的計(jì)算機(jī)通信網(wǎng)絡(luò)。,2,純ALOHA（）,純ALOHA 工作原理 每個(gè)站只要有數(shù)據(jù)發(fā)送，就可自由的發(fā)送一個(gè)數(shù)據(jù)幀,但必須收到接收節(jié)點(diǎn)的確認(rèn)信號(hào)ACK之后，才能發(fā)送下一個(gè)數(shù)據(jù)幀。,AlOHA系統(tǒng)的一般模型,3,純ALOHA（）,

2、圖4-3-2 純ALOHA的工作原理,4,純ALOHA（）,沖突的解決方案 沖突： 兩個(gè)以上的站同時(shí)發(fā)送報(bào)文分組，由于在時(shí)間上重疊從而造成沖突，導(dǎo)致發(fā)送失敗。 解決方案(補(bǔ)救方法) 發(fā)送節(jié)點(diǎn)在一個(gè)timeout interval內(nèi)未收到確認(rèn)信號(hào)ACK,自動(dòng)重發(fā)。,5,時(shí)隙ALOHA(S-ALOHA)(1),目的：為了提高隨機(jī)接入系統(tǒng)的吞吐量，可以將所有各站在時(shí)間上都同步起來(lái)，并將時(shí)間劃分為一段段等長(zhǎng)的時(shí)隙T0, 同時(shí)規(guī)定，不論幀在何時(shí)產(chǎn)生，它只能在每個(gè)時(shí)隙開(kāi)始時(shí)才能發(fā)送出去。這樣的ALOHA系統(tǒng)稱(chēng)為時(shí)隙ALOHA(S-ALOHA)。 工作原理：,6,時(shí)隙ALOHA(S-ALOHA)(2),主要

3、性能參數(shù)： 吞吐率（吞吐量）S -T0 內(nèi)成功發(fā)送的幀數(shù) 0 S 1 網(wǎng)絡(luò)負(fù)載G - T0 內(nèi)總共發(fā)送的平均幀數(shù) T0 的含義：獨(dú)占信道時(shí)成功發(fā)送一幀所用的時(shí)間 幀成功發(fā)送的條件：該幀與其前后2幀的間隔均大于T0,S-ALOHA與ALOHA比較: 重負(fù)載條件下以爭(zhēng)用為基礎(chǔ)的不穩(wěn)定性; 延遲隨提供的負(fù)載按指數(shù)形式增加。,7,4.4 隨機(jī)接入技術(shù)：CSMA（發(fā)前先聽(tīng)),目的：載波監(jiān)聽(tīng)多點(diǎn)接入CSMA是從ALOHA演變出的一種改進(jìn)協(xié)議，又稱(chēng)為載波監(jiān)聽(tīng)多點(diǎn)訪問(wèn)。由于采用了附加的硬件裝置，每個(gè)站都能在發(fā)送數(shù)據(jù)前監(jiān)聽(tīng)信道上其他站是否在發(fā)送數(shù)據(jù)。如在發(fā)送，則此站就暫不發(fā)送數(shù)據(jù)，從而減少了發(fā)送沖突的可能。這樣

4、就提高了整個(gè)系統(tǒng)的吞吐量。 根據(jù)監(jiān)測(cè)時(shí)刻不同，及監(jiān)測(cè)后采用策略的差異，可分為四種: 非堅(jiān)持CSMA(non-persistent CSMA)。 1-堅(jiān)持CSMA P-堅(jiān)持CSMA CSMA/CD:邊聽(tīng)邊發(fā),非堅(jiān)持CSMA,非堅(jiān)持CSMA的工作原理 (a) 監(jiān)聽(tīng)到數(shù)據(jù)閑，則發(fā)送; (b) 監(jiān)聽(tīng)到數(shù)據(jù)“忙”，按一定退避算法延遲一段時(shí)間(這就是。非堅(jiān)持的含義，返回(a)。,優(yōu)點(diǎn): 采用隨機(jī)重傳時(shí)間減少碰撞概率。 缺點(diǎn): 延遲時(shí)間內(nèi)可能會(huì)出現(xiàn)通道閑的情況，利用率不高,9,堅(jiān)持CSMA,堅(jiān)持CSMA的工作原理 堅(jiān)持CSMA的特點(diǎn)是在監(jiān)聽(tīng)到信道忙，仍堅(jiān)持聽(tīng)下去，一直堅(jiān)持聽(tīng)到信道空閑為止。有兩種不同的策略。

5、 1-堅(jiān)持CSMA “1” 的含義是當(dāng)信道一但“閑”,數(shù)據(jù)以概率為1的原則發(fā)送。 （a） 信道一但閑,數(shù)據(jù)以概率為1的原則發(fā)送。 （b）信道忙,連續(xù)監(jiān)聽(tīng)，直至監(jiān)聽(tīng)到通道閑,返回（a）。 優(yōu)點(diǎn):提高信道利用率。 缺點(diǎn):若有兩個(gè)或更多的站同時(shí)在監(jiān)聽(tīng)信道，則一但信道空閑就必然使這些同時(shí)發(fā)送的packet互相沖突。,10,P-堅(jiān)持CSMA,P-堅(jiān)持CSMA的工作原理 （a） 若信道“閑”，以0p1的概率發(fā)送，以概率(1-p)延遲一個(gè)隨機(jī)時(shí)間段再發(fā)送。 （b） 信道忙，則繼續(xù)偵聽(tīng)到信道閑，返回a。 優(yōu)點(diǎn): p堅(jiān)持CSMA可根據(jù)信道上通信量的多少設(shè)定不同的p值，因而可以使信道的利用率進(jìn)一步提高。,Valu

6、e of p?,Avoid instability under heavy load n stations waiting to send End of transmission, expected number of stations attempting to transmit is number of stations ready times probability of transmitting np If np 1on average there will be a collision Repeated attempts to transmit almost guaranteeing

7、 more collisions Retries compete with new transmissions Eventually, all stations trying to send Continuous collisions; zero throughput So np 1 for expected peaks of n If heavy load expected, p small However, as p made smaller, stations wait longer At low loads, this gives very long delays,12,非堅(jiān)持、p堅(jiān)持

8、和1堅(jiān)持這三種的優(yōu)缺點(diǎn),和CSMA一樣，CSMA/CD也可劃分為時(shí)隙和非時(shí)隙的，而這兩種中的每一種又可再分為非堅(jiān)持、p堅(jiān)持和1堅(jiān)持這三種。三種堅(jiān)持各有優(yōu)缺點(diǎn)。 非堅(jiān)持不能充分利用信道剛剛轉(zhuǎn)入空閑期的這段時(shí)間。 1堅(jiān)持又容易在上述這段時(shí)間產(chǎn)生沖突。 p堅(jiān)持可以在一定長(zhǎng)度上克服這些缺點(diǎn)，但卻很難選擇一個(gè)能用于各種通信量強(qiáng)度的p值。,CSMA/CD與CSMA以及ALOGH的吞吐量比較,當(dāng)a=0.01時(shí)幾種CSMA/CD，CSMA以及ALOGH的S-G曲線， 其中：是端到端的時(shí)延,S是吞吐量，G是網(wǎng)絡(luò)負(fù)載,14,CSMA/CD:邊發(fā)邊聽(tīng),CSMA/CD的工作原理 CSMA由于在發(fā)送數(shù)據(jù)之前進(jìn)行載波監(jiān)聽(tīng)

9、，所以減少了沖突的機(jī)會(huì)。但由于傳播時(shí)延的存在，即使發(fā)前先聽(tīng)，沖突還是不可避免的。只要發(fā)生沖突，信道就被浪費(fèi)一段時(shí)間T0+t（沖突時(shí)間+后退時(shí)間）。但CSMA/CD比CSMA又增加了一個(gè)功能，這就是邊發(fā)邊監(jiān)聽(tīng)。只要監(jiān)聽(tīng)到發(fā)生沖突，則沖突的雙方就停止，立即放棄此數(shù)據(jù)幀的發(fā)送。這樣，信道就很快空閑下來(lái)，因而提高了信道的利用率。,CSMA/CD先聽(tīng)后說(shuō)，邊發(fā)邊聽(tīng)，沖突時(shí)退避,With CSMA, collision occupies medium for duration of transmission Stations listen whilst transmitting If medium idl

10、e, transmit, otherwise, step 2 If busy, listen for idle, then transmit If collision detected, jam then cease transmission After jam, wait random time then start from step 1,CSMA/CDOperation,Which Persistence Algorithm?,IEEE 802.3 uses 1-persistent Both nonpersistent and p-persistent have performance

11、 problems 1-persistent (p = 1) seems more unstable than p-persistent Greed of the stations But wasted time due to collisions is short (if frames long relative to propagation delay With random backoff, unlikely to collide on next tries To ensure backoff maintains stability, IEEE 802.3 and Ethernet us

12、e binary exponential backoff,Binary Exponential Backoff,Attempt to transmit repeatedly if repeated collisions First 10 attempts, mean value of random delay doubled Value then remains same for 6 further attempts After 16 unsuccessful attempts, station gives up and reports error As congestion increase

13、s, stations back off by larger amounts to reduce the probability of collision. 1-persistent algorithm with binary exponential backoff efficient over wide range of loads Low loads, 1-persistence guarantees station can seize channel once idle High loads, at least as stable as other techniques Stations

14、 with few collisions transmit first,Collision Detection,On baseband bus, collision produces much higher signal voltage than signal Collision detected if cable signal greater than single station signal Signal attenuated over distance Limit distance to 500m (10Base5) or 200m (10Base2) For twisted pair

15、 (star-topology) activity on more than one port is collision（hub） Special collision presence signal,20,CSMA/CD產(chǎn)生沖突對(duì)信道占用時(shí)間的影響,從圖中可以看出，發(fā)送沖突使A浪費(fèi)時(shí)間TB+TJ(TB是A站從發(fā)送數(shù)據(jù)開(kāi)始到發(fā)現(xiàn)有了沖突的時(shí)間間隔， TJ 是各自都發(fā)送一個(gè)強(qiáng)化沖突的干擾信號(hào)(其持續(xù)時(shí)間) 。同時(shí)，整個(gè)信道被占用的時(shí)間還要增加一個(gè)單程端到端的傳播時(shí)延t。因此總線的爭(zhēng)用期應(yīng)為T(mén)B+TJ+t。TB的最小值為t,最大值為2t。所以爭(zhēng)用期的最小值是2t+TJ,而爭(zhēng)用期的最大值是3t+TJ。

16、,21,CSMA/CD協(xié)議的時(shí)間槽,時(shí)間槽能夠檢測(cè)到?jīng)_突的時(shí)間區(qū)間（也稱(chēng)為爭(zhēng)用時(shí)隙或碰撞窗口） 若兩站點(diǎn)之間傳播時(shí)延為a，則時(shí)間槽2a。,站點(diǎn)2 發(fā)送幀,當(dāng)0時(shí)，將不會(huì)再發(fā)生沖突。這時(shí)，時(shí)間槽2a。,22,時(shí)間槽的意義： 一個(gè)站點(diǎn)開(kāi)始發(fā)送后，若在時(shí)間槽內(nèi)沒(méi)有檢測(cè)到?jīng)_突，則本次發(fā)送不會(huì)再發(fā)生沖突； 時(shí)間槽與網(wǎng)絡(luò)跨距、傳輸速率、最小幀長(zhǎng)有密切的關(guān)系！ 以太網(wǎng)中，時(shí)間槽51.2s 傳輸速率10Mb/s時(shí)，一個(gè)時(shí)間槽內(nèi)可發(fā)送512bits，即64字節(jié)（所以也稱(chēng)一個(gè)時(shí)間槽長(zhǎng)度為64字節(jié)） 。 由此可知： 1. 沖突只可能在一幀的前64字節(jié)內(nèi)發(fā)生； 2. 幀長(zhǎng)度小于64字節(jié)時(shí)，將無(wú)法檢測(cè)出沖突； 以太網(wǎng)規(guī)定，最小幀長(zhǎng)度為64字節(jié) 3. 長(zhǎng)度小于64字節(jié)的幀（碎片幀）都是無(wú)效幀。,23,與時(shí)間槽相關(guān)的網(wǎng)絡(luò)參數(shù),采用CSMA/CD的局域網(wǎng)中，由于時(shí)