chapter4-media acces control layer

1、1Medium Access Control SublayerChapter 4引言 本章講述廣播信道（多路訪問(wèn)信道或隨機(jī)訪問(wèn)信道） 當(dāng)多個(gè)站點(diǎn)共享同一信道時(shí)，如何在不沖當(dāng)多個(gè)站點(diǎn)共享同一信道時(shí)，如何在不沖突的條件下，實(shí)現(xiàn)各站點(diǎn)的消息發(fā)送、接突的條件下，實(shí)現(xiàn)各站點(diǎn)的消息發(fā)送、接收？收？ MAC（medium access control）：用于控制多路訪問(wèn)信道下一個(gè)使用者（某站點(diǎn)）的協(xié)議所在的 數(shù)據(jù)鏈路層的子層4343 X2 - 200523Topicsl4.1 信道分配問(wèn)題l4.2 多路訪問(wèn)協(xié)議l4.3 以太網(wǎng)l4.4 無(wú)線LANl4.5 寬帶無(wú)線l4.6 藍(lán)牙l4.7 RFIDl4.8 數(shù)

2、據(jù)鏈路層交換4Data Link LayerPhysical LayerLogical Link control邏輯鏈路控制子層邏輯鏈路控制子層Medium Access Control sublayer 媒體訪問(wèn)子層媒體訪問(wèn)子層Network LayerlMAC：allocation of multi access channel 處理有關(guān)媒體的訪問(wèn)控制；lLLC：the typical functions in Data link Layer執(zhí)行通常的數(shù)據(jù)鏈路功能。lEthernet only works in MAC subLayer. 以太網(wǎng)沒(méi)有LLC層5lThe MAC sublay

3、er is very important to LANs, especially in Ethernet, in particular because they rely to heavily on the use a multiaccess channel for communication.lThis is mainly because they are broadcast networks as opposed to point-to-point networks. 6lBroadcast channels (multi access channels or random access

4、channels): a number of stations that share the same “wire.”If one station sends, all the others get to hear it.lProblem: if youre sharing a channel, then two or more stations may decide to start frame transmission at the same time, it will lead to frame collision.lMedium Access Control: Allocate the

5、 broadcast channel to one of the competing stations4.1 Allocating Channels(信道分配)7There are two methods of allocating channelslstatic allocation（靜態(tài)劃分）FDMTDMWDMACDMAldynamic allocation（動(dòng)態(tài)劃分）4.1.1 Static Channel Allocation靜態(tài)劃分信道的缺點(diǎn) 利用不充分 不適應(yīng)突發(fā)性的流量4343 X2 - 20058Computer Networks, Fifth Edition by Andre

6、w Tanenbaum and David Wetherall, Pearson Education-Prentice Hall, 20114.1.2 Assumptions for Dynamic Channel AllocationBefore we get to dynamic allocation, we have to consider 5 key assumptionsIndependent trafficSingle channelObservable CollisionsContinuous or slotted time1. Carrier sense or no carri

7、er sense1-independent traffic(流量獨(dú)立) The Model will consist of independent N stations (or terminals). The terminals will produce frames to be transmitted. Once a terminal has produced a frame to transmit, it will block until that frame has been successfully transmitted. 4343 X2 - 200510112 Single Cha

8、nnel Assumption We assume that there will be a single channel for all of the terminals to communicate on. Communication between any two terminals can happen on this channel. All stations are considered to be equivalent. 123 Collision Assumption If two frames are transmitted at the same time, they wi

9、ll “collide”. In a collision, both frames are completely lost. Frames that have collided must be retransmitted at a later time. All stations can detect collisions. There are no errors other than collisions.134 Continuous or slotted TimeTime is treated as a continuum.uThere are no discrete（離散） time i

10、ntervals.uAny terminal can transmit data at any time.Time is treated as a slotted timeu幀的傳輸只能從某個(gè)時(shí)間槽的起始點(diǎn)開(kāi)始u一個(gè)時(shí)間槽可能發(fā)送0個(gè)幀，此時(shí)，時(shí)間槽空閑，即信道空閑1個(gè)幀，成功的發(fā)送多個(gè)幀，沖突145 Carrier/No Carrier Sensel Carrier Sensethe terminal can sense if the channel is busyno terminal will transmit until the channel is idlel No Carrier

11、Sensethe terminal cannot sense if the channel is busyterminals will transmit and check for collisions later.154.2 Multiple Access Protocols（多路訪問(wèn)協(xié)議）lALOHA (pure and slotted)lCarrier Sense （載波監(jiān)聽(tīng)）lCollision-Free（無(wú)沖突協(xié)議）lLimited-Contention Protocols(有限競(jìng)爭(zhēng)協(xié)議)16ALOHAIntroductionALOHA系統(tǒng)由夏威夷大學(xué)的ALOHANET課題組于20世

12、紀(jì)70年代初期研制成功。ALOHANET使分散在4個(gè)島上7個(gè)校園里的計(jì)算機(jī)（遠(yuǎn)程工作站）可以利用無(wú)線傳輸方式與位于瓦胡島的中心計(jì)算機(jī)通信，并通過(guò)中心計(jì)算機(jī)實(shí)現(xiàn)相互通信，避免了鋪設(shè)價(jià)格昂貴的海底通信電纜。ALOHA系統(tǒng)首次將網(wǎng)絡(luò)技術(shù)和無(wú)線通信技術(shù)結(jié)合起來(lái)，最初在無(wú)線信道上實(shí)現(xiàn)，并逐漸在總線式共享信道的有線網(wǎng)絡(luò)中得到應(yīng)用。17Pure ALOHAlDevised in the 70s to solve the channel allocation problem.lIt allows all users to transmit whenever they want, and then check

13、the channel for collisions. 基本思想：只要有待發(fā)數(shù)據(jù)，就讓他們發(fā)lIf a collision occurs, they wait a random period of time and retransmit.lAlthough this works, it is not a very efficient system (18%)4.2.1 ALOHA 發(fā)送方將幀發(fā)送給中央計(jì)算機(jī)，中央計(jì)算機(jī)再將幀廣播出去 發(fā)送站可以收到廣播的幀，從而確定發(fā)送是否成功 不成功，則等待一個(gè)隨機(jī)時(shí)間后，再次重發(fā)4343 X2 - 2005184.2.1 ALOHA19所有幀長(zhǎng)度一樣所有幀

14、長(zhǎng)度一樣In pure ALOHA, frames are transmitted at completely arbitrary（任意的） timesCollisionCollisionTime幀時(shí) 傳輸一個(gè)標(biāo)準(zhǔn)的、固定長(zhǎng)度的幀所需要的時(shí)間 比特時(shí)間？4343 X2 - 20052021Pure ALOHA 假設(shè)ALOHA為一個(gè)定長(zhǎng)幀，數(shù)據(jù)傳輸速率固定且有無(wú)限多個(gè)用戶數(shù)量。在穩(wěn)定的情況下，網(wǎng)絡(luò)吞吐量S(在發(fā)送時(shí)間T0內(nèi)數(shù)據(jù)幀成功發(fā)送的平均數(shù))與網(wǎng)絡(luò)負(fù)載G(亦稱總通信量，每幀時(shí)的平均幀數(shù))之間的關(guān)系為:純純ALOHA性能分析性能分析2GSGe S=P0G P0:成功傳輸?shù)母怕十?dāng)G為輕負(fù)載時(shí)，S

15、G；在G為重負(fù)載下，由于沖突增多，致使S同軸電纜 或 同軸電纜計(jì)算機(jī)l檢測(cè)同軸電纜上的碰撞l在同軸電纜和電纜接口的電子設(shè)備之間進(jìn)行電氣隔離l當(dāng)收發(fā)器或計(jì)算機(jī)出現(xiàn)故障時(shí)，保護(hù)同軸電纜不受影響562、 10BASE2lThe connection to the cable is just a passive BNC T-junction connector(無(wú)源BNC T型連接器). The transceiver electronics are on the controller board. 573、10BASE-TAll the stations are connected to hubDC

16、BA58NIC (Network Interface Card) 網(wǎng)卡Also called network adapter59Function:lSerial/Parallel communication transmission串行/并行轉(zhuǎn)換lBuffer Data 數(shù)據(jù)緩存lFrame Encapsulate and Decapsulate 幀的封裝與解封lImplementation of CSMA/CD CSMA/CD協(xié)議的實(shí)現(xiàn)lManchester Encoding and Decoding曼徹斯特編碼與譯碼CPU高速緩存存儲(chǔ)器I/O 總線計(jì)算機(jī)至局域網(wǎng)網(wǎng)絡(luò)接口卡（網(wǎng)卡）串行通信并

17、行通信60lTo allow larger network , multiple cables are connected by repeaters.lA repeater is a physical Layer devices. It receives, amplifies(regenerate)and retransmits signals in both directions.Repeater (中繼器)614.3.2 The Ethernet MAC Sublayer Protocol1.Working Principle of Ethernet 62lBroadcast Channe

18、l: CSMA/CD-half duplexlConnectionless services lBest effort delivery：unreliable services with no acknowledgement and no sequence number Data link Layer Upper Layerl provide error detection, just drop the wrong frame and do noting else l Data retransmission is done by upper layer, however Ethernet do

19、 not know it is a duplicate frame,and just take it as a new one lManchester Code63There are two different MAC ProtocolslDIX (DEC, Intel, Xerox)was introduced firstwas most widely usedlIEEE 802.3was introduced laterwas not widely used (due to the de facto DIX standard and abundance of available hardw

20、are)they are close enough that it makes little difference2. Ethernet Frame Format64Frame formats. (a)DIX Ethernet, (b)IEEE 802.3.65lPreamble: Seven times 10101010 is used to synchronize the receivers clock with that of the sender.lSOF: Just a delimiter to tell that the real info is now coming.lAddre

21、ss: Generally 48-bit fields. Leftmost bit indicates ordinary（0） or group（1） addresses(目標(biāo)地址最高位為0表示普通地址，1表示組地址). Second bit indicates global（全局地址）or local address（局部地址）.lLength: Ranges from 0-1500. Frames should always be at least 64 bytes.lChecksum: Calculated over the data field. CRC-based.661位1位22位

22、24位I/GG/LSubnet address assigned by IEEE(IEEE指派的子網(wǎng)地址)Physical address assigned by local LAN(當(dāng)?shù)胤峙涞奈锢淼刂?注：I/G(individual / group)0： 個(gè)人地址 1：組地址(group) G/L(GLOBAL / local)0： IEEE指派 1：當(dāng)?shù)刂概?（以太網(wǎng)一般不用G/L 位）67IEEE制定的EUI-48的兩種不同記法802.3 和802.4記法：每個(gè)字節(jié)的高比特在右，低比特在左802.5 和802.6記法：每個(gè)字節(jié)的高比特在左，低比特在右683. Maximum Frame

23、 LengthlThe maximum Frame is up to 1500 bytes. This limit was chosen somewhat arbitrarily , mostly based on the fact that a transceiver needs enough RAM to hold an entire frame in 1978.694. Minimum Frame Length and Contention Period(爭(zhēng)用期)lEthernet requires that valid frames must be at least 64 bytes

24、long, from destination address to checksum, including both.lIf the data portion of frame is less than 46 bytes, the Pad Field is used to fill out the frame to the minimum size.lContention Period：All frames must take more than 2 to send so that the transmission is still taking place when the noise bu

25、rst gets back to the sender in the worst case. 701 kmABtcollisiont = B detect channel is idle and send datat = / 2Collision occurt = 2 A detect collision t = B send dataB detect collision t = ABABAB t = 0 A send dataABt = 0t = B detect collsionAnd stop sendingSTOPt = 2 A detect collisionSTOPABPropag

26、ation time from end to end 71l從幀開(kāi)始發(fā)送到確認(rèn)不會(huì)發(fā)生沖突的時(shí)間稱為爭(zhēng)用期。l最先發(fā)送數(shù)據(jù)幀的站，在發(fā)送數(shù)據(jù)幀后至多經(jīng)過(guò)時(shí)間 2 （兩倍的端到端往返時(shí)延）就可知道發(fā)送的數(shù)據(jù)幀是否遭受了碰撞。l以太網(wǎng)的端到端往返時(shí)延 2 稱為爭(zhēng)用期，或碰撞窗口(collision window)。l經(jīng)過(guò)爭(zhēng)用期這段時(shí)間還沒(méi)有檢測(cè)到碰撞，才能肯定這次發(fā)送不會(huì)發(fā)生碰撞。 爭(zhēng)用期（contention period）72l以太網(wǎng)取 51.2 s 為爭(zhēng)用期的長(zhǎng)度。電磁波在1km電纜的傳播時(shí)延約為5 s 2500米線纜的往返時(shí)間 25.6 s +其他因素（轉(zhuǎn)發(fā)器時(shí)延、碰撞加強(qiáng)的持續(xù)時(shí)間）=5

27、1.2 s l對(duì)于 10 Mb/s 以太網(wǎng)，在爭(zhēng)用期內(nèi)（51.2 s ）可發(fā)送512 bit，即 64 字節(jié)。l以太網(wǎng)在發(fā)送數(shù)據(jù)時(shí)，若前 64 字節(jié)沒(méi)有發(fā)生沖突，則后續(xù)的數(shù)據(jù)就不會(huì)發(fā)生沖突。l幀間隔 9.6us 73最短有效幀長(zhǎng) l如果發(fā)生沖突，就一定是在發(fā)送的前 64 字節(jié)之內(nèi) l由于一檢測(cè)到?jīng)_突就立即中止發(fā)送，這時(shí)已經(jīng)發(fā)送出去的數(shù)據(jù)一定小于 64 字節(jié)。 l以太網(wǎng)規(guī)定了最短有效幀長(zhǎng)為 64 字節(jié)，凡長(zhǎng)度小于 64 字節(jié)的幀都是由于沖突而異常中止的無(wú)效幀。 745、The Binary Exponential Backoff Algorithm delay=k*2。 slot time(ro

28、und-trip delay): 2=51.2 s發(fā)生碰撞的站在停止發(fā)送數(shù)據(jù)后，要推遲（退避）一個(gè)隨機(jī)時(shí)間才能再發(fā)送數(shù)據(jù)。This is an algorithm used to determine how long a station will wait before trying to send again.75AlgorithmlIf a collision occurs between two machines, at the first time they both will wait either 0 or 1 slots before trying again.第一次沖突，各站等

29、待0或1個(gè)時(shí)槽再偵聽(tīng)lIf a collision occurs again(the second time), they will now wait either 0, 1, 2, or 3 slots.第二次沖突，各站等待0、1、2或3個(gè)時(shí)槽再偵聽(tīng)lafter i collisions, a random number k between 0 and 2i-1 is chosen.76lAfter 10 collisions have been reached, the randomization interval is frozen at a maximum of 1023 slots.

30、第十次沖突，隨機(jī)等待最大時(shí)槽固定為 1023個(gè)lAfter 16 collisions, the controller throws in the towel(認(rèn)輸) and reports failure back to the computer.第十六次沖突，控制器向計(jì)算機(jī)報(bào)告?zhèn)魉褪　?7Data frameJam signal TJABTBt B sends dataA senses collisioncollisionT IMEA sends dataWhen A detects collision, it stops sending data immediately and sen

31、ding a jamming signal. B will do the same. Collision Strengthening(強(qiáng)化碰撞): Once the station detects collision, it will send jam signal .發(fā)送數(shù)據(jù)的站一旦發(fā)現(xiàn)沖突，發(fā)送若干比特的人為干擾信號(hào)。78Key Point of CSMA/CDFirst detect then send 先聽(tīng)后發(fā) 2. Sending with detecting 邊聽(tīng)邊發(fā)3. Stop with collision 沖突停發(fā)4. Wait random slots before ret

32、ransmitting 延遲重發(fā) 7980LcTa0If a is low，channel throughtput (信道利用率) will be high4.3.3 Ethernet performace is propagation time ； is sending time L frame length；C data rate； 0T814.3.4 Switched EthernetlProblem: As more stations are added, traffic will go up, and so will the possibility of collisions =th

33、e network will saturate.lSolution: Divide the network into separate sub-LANs and connect them through a high-speed switch.82Each port is a separate collision domain, so collisions do not occur. The total system throughput can often be increased by an order of magnitude over 10BaseT, which has a sing

34、le collision domain for the entire system. 83lFull Duplex(全雙工)lStore-and-forwardlWith no collisionlEach port is an seperate collision domainlSpecial switch fabric chip with high switching date(以太網(wǎng)交換機(jī)由于使用了專用的交換結(jié)構(gòu)芯片，其交換速率就較高)Character of Ethernet Switch84 Switch Taxonomyl second layer switchlThird lay

35、er switch lCut through（直通式）lStore-forward（存儲(chǔ)轉(zhuǎn)發(fā)式）lFragment（碎片式）85hubhubhubDep. 1Dep.3Dep.210BASE-TTo Internet100 Mb/s100 Mb/s100 Mb/sWWWServerEmail Server Switchrouter864.3.5 Fast Ethernet快速（高速）以太網(wǎng)lFast Ethernet (802.3u ): IEEE 802.3 committee keep 802.3 the way it was, but just make it go faster. lB

36、asic Idea: Keep all the data formats, interfaces, and protocols, but just reduce the bit time from 100 nsect o 10 nsec.lThe advantages of 10Base-T wiring were so overwhelming that all fast Ethernet systems use hubs and switches.87lWire types to support： Category 3 twisted pair：100Base-T4 （4 twisted

37、pairs）half duplex, CSMA/CDCategory 5 twisted pair：100Base-TX （2 twisted pairs）Full duplexFiber：100Base-FXOften 100Base-T4 and 100Base-TX are called 100Base-T884.3.6 Gigabit EthernetlGigabit Ethernet(802.3z ): make Ethernet go 10 times faster yet remain backward compatible with all existing Ethernet

38、standards. lGigabit Ethernet works only in point-to-point mode, supporting either full duplex (normal case, used in central switch) or half duplex transmissions(CSMA/CD). Full duplex requires a switch; half duplex can be used with hubs.8990lHalf-duplex mode: used with a hub. A hub does not buffer in

39、coming frames. So Collisions are possible, CSMA/CD protocol required. lSince a minimum frame(64Bytes), however the data can now be transmitted 100 times faster than in classic Ethernet (10M 1000M), the maximum distance is 100 times less, or 25 meters (2500m25m).l The radius of 25 meters is unaccepta

40、ble, so that two features are introduced to increase the radius91LcTa0There are two features to extend the radius of the network to 200 meters1、Carrier extension載波延伸tells the hardware to add its own padding after the normal frame(64 bytes) to extend the frame to 512 bytes. 幀格式和最短幀長(zhǎng)不變（512bit），在原來(lái)的幀上加

41、一些無(wú)效擴(kuò)展，到512字節(jié)。（不足512字節(jié)時(shí)擴(kuò)展）922、Frame bursting分組突發(fā) allows a sender to transmit a concatenated （連接、拼接） sequence of multiple frames in a single transmission.當(dāng)發(fā)送多個(gè)短幀時(shí)，只有第一個(gè)幀加擴(kuò)展，隨后的一些短幀可以一個(gè)接一個(gè)地發(fā)送，中間有必要的最小間隔，但總長(zhǎng)度不超過(guò)1500字節(jié)。93lGigabit Ethernet supports both copper and fiber cabling Figure 423. Gigabit Ethern

42、et cabling.944.3.7 10 Gigabit Ethernetl10-gigabit Ethernet-802.3ae (2002)l1000baseT remain backward compatible with ethernet data formats and frame length. Only works in Full- duplex, CSMA/CD protocol is not required Only take use of Fiber Data rate is954.4 Wireless LANSlThe 802.11 Protocol StacklTh

43、e 802.11 Physical LayerlThe 802.11 MAC SublayerProtocollThe 802.11 Frame StructurelThe 802.11 Services96802.11(WLAN) vs. 802.3(Ethernet)lThe range of a single radio may not cover the entire system.lMultipathfading: a radio signal can be reflected off solid objects, so it may be received multiple tim

44、es along multiple paths.lHand-off: When notebook moves between base stations, some way of handing it off is needed.lA great deal of software is not aware of mobilitylSecurity is even more important for wireless systems than for wired ones4.4.1 The 802.11Architecture and Protocol Stack97Two Modes of

45、Wireless LANsThe 802.11 standard had to work in two modes:lIn the presence of a base station: all communication was to go through the base station, called an access pointlIn the absence of a base station: the computers would just send to one another directly. Called ad hoc (a) Wireless networking wi

46、th a base station.(b) Ad hoc networking.99Part of the 802.11 protocol stack.802.11b : WiFi100StandardSpectrumBit RateTransmissionCompatibility802.11wavelength between 850 and 950 nm;2.4 GHz2 MbpsInfrared / FHSS / DSSSN/A802.11a5.0 GHz54 MbpsOFDMNone802.11b (Wi-Fi)2.4 GHz11 MbpsDSSS802.11802.11g2.4 G

47、Hz54 MbpsOFDM802.11 / 802.11b1014.4.2 The 802.11 Physical LayerlInfrared: Applicable for 1-2 Mbps. Not very popular, also because sunlight degrades performance.lFHSS (Frequency Hopping Spread Spectrum): Use 79 channels, each 1 MHz wide starting at the low end of the 2.4-GHz ISM band. In effect, fram

48、es are sent at different frequencies each time. Low bandwidth, but good resistance against security attacks and interference from other devices.lDSSS (Direct Sequence Spread Spectrum): Similar to CDMA, restricted to 1-2 Mbps.102lOrthogonal FDM(802.11a): Akin to ADSL: apply FDM across multiple channe

49、ls (48 for data, 4 for control) in 5-GHz ISM band. Can reach 54 Mbps. lHR-DSSS (802.11b): Consider it enhanced CDMA to get to 11 Mbps. Use the 2.4-GHz ISM band. It is the most common and is the WiFistandard.l802.11g: It uses the OFDM modulation method of 802.11a but operates in the narrow 2.4-GHz IS

50、M band along with 802.11b. Can operate at up to 54 Mbps.1031044.4.3 The 802.11 MAC Sublayer Protocol lIn wireless LANs, not all stations are within range of one another, which leads to a variety of complications: the hidden/exposed station problem.lMost radios are half duplex, they cannot transmit a

51、nd listen for noise bursts at the same time on a single frequencylThe Ethernet CSMS/CD cant be used in 802.11，and an acknowledgement is required Range of As radioRange of Cs radioABCDl Since A and C cant sense wireless signal, they consider B is idle. lWhen the data is transmitted to B, it will inte

52、rfere at BThe hidden station problem results when one station is transmitting data but a second station cannot “hear” the transmission and starts transmitting.Range of Bs radioRange of Cs radioADCB？C wants to communicate with D while B sending data to A. C hear an ongoing transmission and falsely co

53、nclude that it may not send to DThe exposed station problem results when one station refrains from transmitting data due to another transmission that would not have affected the data transfer107Solutions lDCF (Distributed Coordination Function): let the stations figure it out by using a collision av

54、oidance protocol (CSMA/CA).Would like to use CSMANice for bursty trafficcant use CD, But use Collision Avoidance insteadlPCF (Point Coordination Function): Let a single base station control who gets to send a frame. Since transmission order is completely controlled by the base station, no collisions

55、 ever occur. All 802.11 implementations must support DCF but PCF is optional. 108Multiple Access with Collision AvoidancelThe sender sends a a short frame RTS to stimulate the receiver into outputting a CTS, so stations nearby can detect this transmission and avoid transmitting for the duration of t

56、heupcoming data frame. lWhen collision occurs, uses binary exponential backoffalgorithm.lMACAW (MACA for Wireless) is a fine tuned version.(a)A sending an RTS to B. (b)B responding with a CTS to 109MACAW(multi access collision avoidance for wireless)lBasically a refined MACA for Wroduced

57、an ACK frame after each successful data roduced carrier sensing to prevent stations from transmitting RTSs to the same destination and at the same time as other stations.added a mechanism for stations to exchange data about congestion to improve system performance.110CSMA/CAlCSMA: Ethernet-

58、like. Sense the channel and send only if its free. Dont sense the channel during transmission: if a collision occurred, wait a random time and try again later.lCA: MACAW-like. Send RTS/CTS packets to see where you are and whether you should defer transmission to avoid interference with a transmissio

59、n between two other stations111NAV (Network Allocation Vector): Its a virtual channel that a station assigns to itself telling it to shut up.The use of virtual channel sensing using CSMA/CA112lWireless networks are noisy and unreliable, the probability of a frame making it through successfully decre

60、ases with frame length. l802.11 allows frames to be fragmented into smaller pieces, which can be sent in a row (fragment burst ) and are individually acknowledged using a stop-and-wait protocol. 113Interframe spacing mechanism in 802.11 allows: l a whole fragment burst to be sent without interferenc