山東大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)英語(yǔ)課件04Medium Access Control Sublayer

1、Medium Access Control SublayerChapter 4CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Channel Allocation ProblemMultiple Access ProtocolsEthernetWireless LANsBroadband WirelessBluetoothRFIDData Link Layer SwitchingRevised: August 2011The MAC SublayerCN5E by Tane

2、nbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Responsible for deciding who sends next on a multi-access linkAn important part of the link layer, especially for LANsPhysicalLinkNetworkTransportApplicationMAC is in here!Channel Allocation Problem (1)For fixed channel and tra

3、ffic from N usersDivide up bandwidth using FTM, TDM, CDMA, etc. This is a static allocation, e.g., FM radioThis static allocation performs poorly for bursty trafficAllocation to a user will sometimes go unused CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Chann

4、el Allocation Problem (2)Dynamic allocation gives the channel to a user when they need it. Potentially N times as efficient for N users.Schemes vary with assumptions:Assumption ImplicationIndependent trafficOften not a good model, but permits analysisSingle channelNo external way to coordinate sende

5、rsObservable collisionsNeeded for reliability; mechanisms varyContinuous or slotted timeSlotting may improve performanceCarrier senseCan improve performance if availableCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Multiple Access ProtocolsCN5E by Tanenbaum & W

6、etherall, Pearson Education-Prentice Hall and D. Wetherall, 2011ALOHA CSMA (Carrier Sense Multiple Access) Collision-free protocols Limited-contention protocols Wireless LAN protocols ALOHA (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011In pure ALOHA, users t

7、ransmit frames whenever they have data; users retry after a random time for collisionsEfficient and low-delay under low loadCollisionCollisionTimeUserABCDEALOHA (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Collisions happen when other users transmit during

8、a vulnerable period that is twice the frame timeSynchronizing senders to slots can reduce collisionsALOHA (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Slotted ALOHA is twice as efficient as pure ALOHALow load wastes slots, high loads causes collisions Effic

9、iency up to 1/e (37%) for random traffic modelsCSMA (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011CSMA improves on ALOHA by sensing the channel!User doesnt send if it senses someone elseVariations on what to do if the channel is busy:1-persistent (greedy) se

10、nds as soon as idleNonpersistent waits a random time then tries againp-persistent sends with probability p when idleCSMA (2) PersistenceCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011CSMA outperforms ALOHA, and being less persistent is better under high loadCSMA

11、 (3) Collision DetectionCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011CSMA/CD improvement is to detect/abort collisionsReduced contention times improve performanceCollision time is much shorter than frame timeCollision-Free (1) BitmapCN5E by Tanenbaum & Wethera

12、ll, Pearson Education-Prentice Hall and D. Wetherall, 2011Collision-free protocols avoid collisions entirelySenders must know when it is their turn to send The basic bit-map protocol:Sender set a bit in contention slot if they have dataSenders send in turn; everyone knows who has dataCollision-Free

13、(2) Token RingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Token sent round ring defines the sending orderStation with token may send a frame before passingIdea can be used without ring too, e.g., token busStationDirection oftransmissionTokenCollision-Free (3)

14、 CountdownCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Binary countdown improves on the bitmap protocolStations send their address in contention slot (log N bits instead of N bits)Medium ORs bits; stations give up when they send a “0” but see a “1”Station that

15、 sees its full address is next to sendLimited-Contention Protocols (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Idea is to divide stations into groups within which only a very small number are likely to want to send Avoids wastage due to idle periods and co

16、llisionsAlready too many contenders for a good chance of one winnerLimited Contention (2) Adaptive Tree WalkCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Tree divides stations into groups (nodes) to pollDepth first search under nodes with poll collisionsStart s

17、earch at lower levels if 1 station expectedLevel 0Level 1Level 2Wireless LAN Protocols (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Wireless has complications compared to wired.Nodes may have different coverage regionsLeads to hidden and exposed terminalsNo

18、des cant detect collisions, i.e., sense while sendingMakes collisions expensive and to be avoidedWireless LANs (2) Hidden terminalsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Hidden terminals are senders that cannot sense each other but nonetheless collide at

19、 intended receiverWant to prevent; loss of efficiencyA and C are hidden terminals when sending to BWireless LANs (3) Exposed terminalsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Exposed terminals are senders who can sense each other but still transmit safely

20、(to different receivers) Desirably concurrency; improves performanceB A and C D are exposed terminalsWireless LANs (4) MACA CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011MACA protocol grants access for A to send to B:A sends RTS to B left; B replies with CTS ri

21、ght A can send with exposed but no hidden terminalsA sends RTS to B; C and E hear and defer for CTSB replies with CTS; D and E hear and defer for dataEthernetCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Classic Ethernet Switched/Fast Ethernet Gigabit/10 Gigabi

22、t Ethernet Classic Ethernet (1) Physical LayerCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011One shared coaxial cable to which all hosts attachedUp to 10 Mbps, with Manchester encodingHosts ran the classic Ethernet protocol for accessClassic Ethernet (2) MAC CN5

23、E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011MAC protocol is 1-persistent CSMA/CD (earlier)Random delay (backoff) after collision is computed with BEB (Binary Exponential Backoff) Frame format is still used with modern Ethernet.Ethernet(DIX)IEEE 802.3Classic Ethe

24、rnet (3) MACCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Collisions can occur and take as long as 2 to detect is the time it takes to propagate over the EthernetLeads to minimum packet size for reliable detectionClassic Ethernet (4) PerformanceCN5E by Tanenbau

25、m & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Efficient for large frames, even with many sendersDegrades for small frames (and long LANs)10 Mbps Ethernet,64 byte min. frameSwitched/Fast Ethernet (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall

26、, 2011Hubs wire all lines into a single CSMA/CD domainSwitches isolate each port to a separate domainMuch greater throughput for multiple portsNo need for CSMA/CD with full-duplex linesSwitched/Fast Ethernet (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Swit

27、ches can be wired to computers, hubs and switchesHubs concentrate traffic from computers More on how to switch frames the in 4.8 SwitchTwisted pairSwitch portsHubSwitched/Fast Ethernet (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Fast Ethernet extended Ethe

28、rnet from 10 to 100 MbpsTwisted pair (with Cat 5) dominated the marketGigabit / 10 Gigabit Ethernet (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Switched Gigabit Ethernet is now the garden varietyWith full-duplex lines between computers/switchesGigabit / 10

29、 Gigabit Ethernet (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Gigabit Ethernet is commonly run over twisted pair10 Gigabit Ethernet is being deployed where needed40/100 Gigabit Ethernet is under developmentWireless LANsCN5E by Tanenbaum & Wetherall, Pearso

30、n Education-Prentice Hall and D. Wetherall, 2011802.11 architecture/protocol stack 802.11 physical layer 802.11 MAC 802.11 frames 802.11 Architecture/Protocol Stack (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Wireless clients associate to a wired AP (Acces

31、s Point)Called infrastructure mode; there is also ad-hoc mode with no AP, but that is rare.AccessPointClientTo Network802.11 Architecture/Protocol Stack (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011MAC is used across different physical layers802.11 physical

32、 layerCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011NICs are compatible with multiple physical layersE.g., 802.11 a/b/gNameTechniqueMax. Bit Rate802.11bSpread spectrum, 2.4 GHz11 Mbps802.11gOFDM, 2.4 GHz54 Mbps802.11aOFDM, 5 GHz54 Mbps802.11nOFDM with MIMO, 2.4

33、/5 GHz600 Mbps802.11 MAC (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011CSMA/CA inserts backoff slots to avoid collisionsMAC uses ACKs/retransmissions for wireless errors802.11 MAC (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wethe

34、rall, 2011Virtual channel sensing with the NAV and optional RTS/CTS (often not used) avoids hidden terminals802.11 MAC (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Different backoff slot times add quality of serviceShort intervals give preferred access, e.g

35、., control, VoIPMAC has other mechanisms too, e.g., power save802.11 FramesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Frames vary depending on their type (Frame control)Data frames have 3 addresses to pass via APsBroadband WirelessCN5E by Tanenbaum & Wethera

36、ll, Pearson Education-Prentice Hall and D. Wetherall, 2011802.16 Architecture / Protocol Stack 802.16 Physical Layer 802.16 MAC 802.16 Frames 802.16 Architecture/Protocol Stack (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Wireless clients connect to a wired

37、 basestation (like 3G)802.16 Architecture/Protocol Stack (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011MAC is connection-oriented; IP is connectionlessConvergence sublayer maps between the two802.16 Physical LayerCN5E by Tanenbaum & Wetherall, Pearson Educat

38、ion-Prentice Hall and D. Wetherall, 2011Based on OFDM; base station gives mobiles bursts (subcarrier/time frame slots) for uplink and downlink802.16 MACCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Connection-oriented with base station in controlClients request

39、 the bandwidth they needDifferent kinds of service can be requested:Constant bit rate, e.g., uncompressed voiceReal-time variable bit rate, e.g., video, WebNon-real-time variable bit rate, e.g., file downloadBest-effort for everything else802.16 FramesCN5E by Tanenbaum & Wetherall, Pearson Education

40、-Prentice Hall and D. Wetherall, 2011Frames vary depending on their typeConnection ID instead of source/dest addresses(a) A generic frame. (b) A bandwidth request frame(b)(a)BluetoothCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Bluetooth Architecture Bluetooth

41、 Applications / Protocol Bluetooth Radio / Link Layers Bluetooth Frames Bluetooth ArchitectureCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Piconet master is connected to slave wireless devicesSlaves may be asleep (parked) to save power Two piconets can be brid

42、ged into a scatternetBluetooth Applications / Protocol StackCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Profiles give the set of protocols for a given application25 profiles, including headset, intercom, streaming audio, remote control, personal area network,

43、 Bluetooth Radio / Link LayersCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Radio layerUses adaptive frequency hopping in 2.4 GHz bandLink layerTDM with timeslots for master and slavesSynchronous CO for periodic slots in each directionAsynchronous CL for packet

44、-switched dataLinks undergo pairing (user confirms passkey/PIN) to authorize them before useBluetooth FramesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Time is slotted; enhanced data rates send faster but for the same time; addresses are only 3 bits for 8 dev

45、ices(b)(a)(a)(b)RFIDCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Gen 2 Architecture Gen 2 Physical Layer Gen 2 Tag Identification Layer Gen 2 Frames Gen 2 ArchitectureCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Reader s

46、ignal powers tags; tags reply with backscatterGen 2 Physical LayerCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Reader uses duration of on period to send 0/1Tag backscatters reader signal in pulses to send 0/1Gen 2 Tag Identification LayerCN5E by Tanenbaum & We

47、therall, Pearson Education-Prentice Hall and D. Wetherall, 2011Reader sends query and sets slot structureTags reply (RN16) in a random slot; may collideReader asks one tag for its identifier (ACK)Process continues until no tags are leftGen 2 FramesCN5E by Tanenbaum & Wetherall, Pearson Education-Pre

48、ntice Hall and D. Wetherall, 2011Reader frames vary depending on type (Command)Query shown below, has parameters and error detectionTag responses are simply dataReader sets timing and knows the expected formatQuery messageData Link Layer SwitchingCN5E by Tanenbaum & Wetherall, Pearson Education-Pren

49、tice Hall and D. Wetherall, 2011Uses of Bridges Learning Bridges Spanning Tree Repeaters, hubs, bridges, ., routers, gateways Virtual LANs Uses of BridgesCommon setup is a building with centralized wiringBridges (switches) are placed in or near wiring closetsCN5E by Tanenbaum & Wetherall, Pearson Ed

50、ucation-Prentice Hall and D. Wetherall, 2011Learning Bridges (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011A bridge operates as a switched LAN (not a hub)Computers, bridges, and hubs connect to its ports Learning Bridges (2)CN5E by Tanenbaum & Wetherall, Pea

51、rson Education-Prentice Hall and D. Wetherall, 2011Backward learning algorithm picks the output port:Associates source address on frame with input portFrame with destination address sent to learned portUnlearned destinations are sent to all other portsNeeds no configurationForget unused addresses to

52、 allow changesBandwidth efficient for two-way trafficLearning Bridges (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Bridges extend the Link layer:Use but dont remove Ethernet header/addressesDo not inspect Network headerSpanning Tree (1) Problem CN5E by Tane

53、nbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Bridge topologies with loops and only backward learning will cause frames to circulate for everNeed spanning tree support to solve problemSpanning Tree (2) AlgorithmCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Subset of forwarding ports for data is use to avoid loopsS