Data Link ProtocolsLink Layer Services Framing, Addressing, link access: encapsulate datagram into frame, adding header, trailer channel access if shared medium “MAC” addresses used in frame headers to identify source, dest  different from IP address! Error Detection: errors caused by signal attenuation, noise.  receiver detects presence of errors:  signals sender for retransmission or drops frameMedium Access Control (MAC) ProtocolsMAC Protocols: a taxonomyThree broad classes: Channel Partitioning divide channel into smaller “pieces” (time slots, frequency, code) allocate piece to node for exclusive use Random Access channel not divided, allow collisions “recover” from collisions “Taking turns” Nodes take turns, but nodes with more to send can take longer turnsChannel Partitioning MAC protocols: TDMATDMA: time division multiple access access to channel in "rounds"  each station gets fixed length slot (length = pkt trans time) in each round  unused slots go idle  example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle Channel Partitioning MAC protocols: FDMAFDMA: frequency division multiple access channel spectrum divided into frequency bands each station assigned fixed frequency band unused transmission time in frequency bands go idle  example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle  TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. FDM (Frequency Division Multiplexing): frequency subdivided.frequency bandstimeRandom Access Protocols When node has packet to send transmit at full channel data rate R. no a priori coordination among nodes two or more transmitting nodes ➜ “collision”, random access MAC protocol specifies:  how to detect collisions how to recover from collisions (e.g., via delayed retransmissions) Examples of random access MAC protocols: slotted ALOHA ALOHA CSMA, CSMA/CD, CSMA/CAEthernet uses CSMA/CD No slots adapter doesn’t transmit if it senses that some other adapter is transmitting, that is, carrier sense transmitting adapter aborts when it senses that another adapter is transmitting, that is, collision detection Before attempting a retransmission, adapter waits a random time, that is, random accessEthernet CSMA/CD algorithm1. Adaptor receives datagram from net layer & creates frame2. If adapter senses channel idle, it starts to transmit frame. If it senses channel busy, waits until channel idle and then transmits3. If adapter transmits entire frame without detecting another transmission, the adapter is done with frame !4. If adapter detects another transmission while transmitting, aborts and sends jam signal5. After aborting, adapter enters exponential backoff: after the mthcollision, adapter chooses a K at random from {0,1,2,…,2m-1}. Adapter waits K·512 bit times and returns to Step 2IEEE 802.11 Wireless LAN 802.11b 2.4-5 GHz unlicensed radio spectrum up to 11 Mbps direct sequence spread spectrum (DSSS) in physical layer all hosts use same chipping code widely deployed, using base stations 802.11a 5-6 GHz range up to 54 Mbps 802.11g 2.4-5 GHz range up to 54 Mbps All use CSMA/CA for multiple access All have base-station and ad-hoc network versions802.11 LAN architecture wireless host communicates with base station base station = access point (AP) Basic Service Set (BSS)(aka “cell”) in infrastructure mode contains: wireless hosts access point (AP): base station ad hoc mode: hosts onlyBSS 1BSS 2Internethub, switchor routerAPAP802.11: Channels, association 802.11b: 2.4GHz-2.485GHz spectrum divided into 11 channels at different frequencies AP admin chooses frequency for AP interference possible: channel can be same as that chosen by neighboring AP! host: must associate with an AP scans channels, listening for beacon framescontaining AP’s name (SSID) and MAC address selects AP to associate with may perform authentication [Chapter 8] will typically run DHCP to get IP address in AP’s subnetIEEE 802.11: multiple access avoid collisions: 2+nodes transmitting at same time 802.11: CSMA - sense before transmitting don’t collide with ongoing transmission by other node 802.11: no collision detection! difficult to receive (sense collisions) when transmitting due toweak received signals (fading) can’t sense all collisions in any case: hidden terminal, fading goal: avoid collisions: CSMA/C(ollision)A(voidance)ABCABCA’s signalstrengthspaceC’s signalstrengthIEEE 802.11 MAC Protocol: CSMA/CA802.11 sender1 if sense channel idle for DIFS thentransmit entire frame (no CD)2 if sense channel busy thenstart random backoff timetimer counts down while channel idletransmit when timer expiresif no ACK, increase random backoff interval, repeat 2802.11 receiver- if frame received OKreturn ACK after SIFS (ACK needed due to hidden terminal problem) senderreceiverDIFSdataSIFSACKAvoiding collisions (more)idea: allow sender to “reserve” channel rather than random access of data frames: avoid collisions of long data frames sender first transmits small request-to-send (RTS) packets to BS using CSMA RTSs may still collide with each other (but they’re short) BS broadcasts clear-to-send CTS in response to RTS RTS heard by all nodes sender transmits data frame other stations defer transmissions Avoid data frame collisions completely using small reservation packets!Collision Avoidance: RTS-CTS exchangeAPABtimeRTS(A)RTS(B)RTS(A)CTS(A)CTS(A)DATA (A)ACK(A)ACK(A)reservation collisiondeferframecontroldurationaddress1address2address4address3payload CRC22 66 6 260 - 23124seqcontrol802.11 frame: addressingAddress 2: MAC addressof wireless host or AP transmitting this frameAddress 1: MAC addressof wireless host or AP to receive this frameAddress 3: MAC addressof router interface to which AP is attachedAddress 3: used only in ad hoc modeInternetrouterAPH1R1AP MAC addr H1 MAC addr R1 MAC addraddress 1address 2address 3802.11 frameR1 MAC addr AP MAC addr dest. address source address 802.3 frame802.11 frame: addressingframecontroldurationaddress1address2address4address3payload CRC22 66 6 260 - 23124seqcontrolTypeFromAPSubtypeToAPMore fragWEPMoredataPowermgtRetry RsvdProtocolversion22 4 11 1 1 1111802.11 frame: