CSC 570 Computer Networks 2024 PDF

5/14/24 Medium Access Control– Systems (I) CSC 570 Computer Networks 2024 1 Networking Systems 1. Ethernet 2. Wireless LANs 3. Broadband wireless 4. Bluetooth 5. RFID Khaled Harfoush 2...

5/14/24 Medium Access Control– Systems (I) CSC 570 Computer Networks 2024 1 Networking Systems 1. Ethernet 2. Wireless LANs 3. Broadband wireless 4. Bluetooth 5. RFID Khaled Harfoush 2 1  5/14/24 Ethernet § Wired Network § IEEE standard 802.3 § Two Ethernet types: 1. Classic Ethernet 2. Switched Ethernet A. Fast Ethernet B. Gigabit Ethernet C. 10 Gigabit Ethernet Khaled Harfoush 3 1. Classic Ethernet § One shared coaxial cable to which all hosts attached n Physical layer uses Manchester encoding for synchronization n Cable up-to 185 meters per coax segment handling at most 30 machines (why? Has to do with MAC protocol - next) n Up to 10 Mbps Khaled Harfoush 4 2  5/14/24 Frame Format § Data size is at least 46 bytes and at most 1500 bytes – Maximum Transfer Unit (MTU) is 1500 bytes (why? Has to do with MAC protocol - next) § Destination address could be a unicast, broadcast, or multicast address. Source address should be --- 8 6 6 2 0-1500 0-46 4 IEEE 802.3 Length/type 32-bit CRC Khaled Harfoush 5 MAC Protocol § is CSMA/CD § Random delay (backoff) after collision is computed with BEB (Binary Exponential Backoff) § After a collision, time is divided into discrete slots whose length is equal to 2t (51.2μsec) § After 1st collision, a STA waits for 0 or 1 slot times before trying again § After 2nd collision, a STA waits for 0, 1, 2, or 3 slot times before trying again § After 10th collision, a STA waits for x slots, where x is chosen at random between 0 and 210-1 § Further collisions leads to freezing the randomization Khaled Harfoush 6 3  5/14/24 CSMA/CD § When a station has data to send: 1. Sense to the channel to see if anyone else is transmitting. 2. If channel is idle then transmit frame detect collision for a 2t period (contention slot) If collision detected then 1) Abort transmission 2) Wait for a random period (follow BEB) 2) Start all over Else 1) Wait for a random period (follow BEB) 2) Start all over Khaled Harfoush 7 CSMA/CD Life Stages Collision time is much shorter than frame time Khaled Harfoush 8 4  5/14/24 Collision Detection § Collisions can occur and take as long as 2t to detect n t is the time it takes to propagate over the Ethernet n Leads to minimum packet size for reliable detection (why?) Khaled Harfoush 9 Reasons for max/min frame size § Max size (MTU) defines the RAM size at transceivers (need enough bytes to hold a frame). At the time Ethernet was introduced (1978) RAM was expensive § Min size is to ensure that each frame takes at least 2t amount of time to transmit on the cable. Recall that collisions are detected while transmitting a frame, and it takes at least 2t amount of time to detect collisions Khaled Harfoush 10 5  5/14/24 Classic Ethernet Performance (1/3) Khaled Harfoush 11 Classic Ethernet Performance (2/3) slot interval Khaled Harfoush 12 6  5/14/24 Classic Ethernet Performance (3/3) Channel Efficiency is proportional to frame size, P, and inversely proportional to cable length, t Khaled Harfoush 13 Efficiency Recap Khaled Harfoush 14 7  5/14/24 Ethernet using Hubs § Hubs are PHY layer devices. They only relay bits. Nothing more. § Wires all lines into a single collision domain § Ethernet STAs can be connected through hub instead of using a long cable – same performance Khaled Harfoush 15 2. Switched Ethernet § Uses a switch to connect user cables (instead of long cable or hub) § Makes it easier to manage cables/identify problems § Switches and hubs look similar but are very different Switch Hub ports Twisted pair/fiber Khaled Harfoush 16 8  5/14/24 Hubs vs Switches n Hubs (layer 1 devices) wire all lines into a single collision domain (CSMA/CD still needed) n Switches (layer 2 devices) isolate each port to a separate collision domain (CSMA/CD not needed with full-duplex lines) Khaled Harfoush 17 Switch Details § Receiving a frame over one port, the switch transmits the frame using the port corresponding to the frame’s destination MAC address. So, need to be able to 1. Associate STAs MAC addresses with ports 2. Need to queue incoming frames 3. Check an incoming frame destination MAC address in Layer 2 header 4. Transmit frame over corresponding port Khaled Harfoush 18 9  5/14/24 Advantages of Switches 1. No collisions so capacity is used more efficiently 2. Multiple frames can be sent simultaneously by multiple STAs – Switch needs buffering though 3. Frames between two STAs are not observed by other STAs – Security benefit Khaled Harfoush 19 Switched Ethernet Variants A. Fast Ethernet (100 Mbps) B. Gigabit Ethernet (1 Gbps) C. 10-Gigabit Ethernet (10 Gbps) Khaled Harfoush 20 10  5/14/24 Switched Ethernet Details § Improvements in performance made possible with 1. Cable from twisted pair CAT 3 to CAT 5 to fiber 2. Using higher clocking speeds and higher bandwidth 3. More signal levels (symbols) § Backward compatibility still maintained through a negotiation step § CSAM/CD still used when there hubs in the network so cable lengths and frame size relation still needs to be maintained in order to detect collisions in this case Khaled Harfoush 21 Networking Systems 1. Ethernet 2. Wireless LANs 3. Broadband wireless 4. Bluetooth 5. RFID Khaled Harfoush 22 11  5/14/24 Wireless LANs § Wireless Network! Leads to different design choices than in the wired Ethernet case § IEEE standard 802.11 § Two Ethernet types: 1. Infrastructure mode -- Access Points (AP) connect nodes. Most common 2. Ad-hoc mode – Nodes communicate directly, without APs Khaled Harfoush 23 802.11 Architecture Wireless clients associate to a wired AP To Network Access Point Client Khaled Harfoush 24 12  5/14/24 802.11 Protocol Stack MAC is used across different physical layers Khaled Harfoush 25 802.11 physical layer n NICs are compatible with multiple physical layers, e.g., 802.11 a/b/g Name Technique Max. Bit Rate 802.11b Spread spectrum, 2.4 GHz 11 Mbps 802.11g OFDM, 2.4 GHz 54 Mbps 802.11a OFDM, 5 GHz 54 Mbps 802.11n OFDM with MIMO, 2.4/5 GHz 600 Mbps Khaled Harfoush 26 13  5/14/24 802.11 MAC § Collision detection not possible. Why? 1. Radios are almost always half-duplex. STAs cannot transmit and listen for noise/collisions at the same time § Solution? CSMA/CA instead of CSMA/CD 2. The transmission range of different STAs may be different. Hidden and exposed terminal issues appear § Hidden terminals lead to collisions and exposed terminals expose collisions which should not be affecting the transmission. § Solution? NAV Khaled Harfoush 27 CSMA/CA § Carrier Sense Multiple Access with Collision Avoidance § Uses ACKs/retransmissions for wireless errors § Inserts backoff slots to avoid collisions § When ready to transmit § Compute a backoff value (random number of time slots) § Sense if channel is free If (free and backoff expired) then transmit frame If (free and backoff did not expire) then wait for backoff If (busy) then put backoff on hold till channel is free Khaled Harfoush 28 14  5/14/24 CSMA/CA Example Khaled Harfoush 29 But then … § What about hidden and exposed terminal issues? § Recall Multiple Access with Collision Avoidance (MACA) protocol? Khaled Harfoush 30 15  5/14/24 MACA Protocol Relies and short (30 bytes) RTS and CTS frames n RTS ≡ Request To Send, CTS ≡ Clear To Send n A sends RTS to B [left]; B replies with CTS [right] A sends RTS to B; C and E B replies with CTS; D and E hear and defer for CTS Khaled Harfoush hear and defer for data 31 MACA Recap § By using short RTS/CTS frames and having STAs wait for CTS or for Data, MACA helps to resolve the hidden/exposed terminal issue Khaled Harfoush 32 16  5/14/24 Q 1. Does MACA solve the exposed terminal problem? 2. Does MACA help with he exposed terminal problem? 3. Does MACA solve the hidden terminal problem? 4. Does MACA help with he hidden terminal problem? Khaled Harfoush 33 802.11 Dealing with Exposed and Hidden Terminals § 802.11 uses a variant of MACA in which 1. It still relies on RTS/CTS (short frames) – These are optional 2. A STA hearing an RTS or a CTS frames assumes the channel will be busy for the duration of the frame and the corresponding ACK (and the CTS frame). What are the implications? § Instead of waiting only for CTS when hearing an RTS frame § The frame length is revealed in RTS/CTS/Data NAV fields Khaled Harfoush 34 17  5/14/24 NAV § Network Allocation Vector § Each frame carries a NAV field that says how long it will take to complete § STAs that overhear the NAV know for how long the channel will be busy Khaled Harfoush 35 Virtual Channel Sensing using NAV Fields § Virtual channel sensing with the NAV and optional RTS/CTS Khaled Harfoush 36 18  5/14/24 Q 1. Does 802.11 RTS/CTS/NAV solve the exposed terminal problem? 2. Does 802.11 RTS/CTS/NAV help with the exposed terminal problem? 3. Does 802.11 RTS/CTS/NAV solve the hidden terminal problem? 4. Does 802.11 RTS/CTS/NAV help with the hidden terminal problem? Khaled Harfoush 37 RTS/CTS Overhead 1. Overhead especially for short frames 2. Does not help for AP frames, which all STAs would hear – So not hidden/exposed terminal issues anyway. § Most of the frames are from the AP. Why? 3. Does not help with exposed terminal problem. Why? 4. When there are few hidden terminals, CSMA/CA helps them without RTS/CTS by slowing down stations submitting unsuccessfully through backoff Khaled Harfoush 38 19  5/14/24 Ethernet Extra Features 1. Frame fragmentation to improve channel efficiency 2. Power saving 3. Quality of Service Khaled Harfoush 39 1. Fragmentation § Shorter frames have a better chance at getting through undamaged – As opposed to Ethernet in which larger frames provide better channel efficiency – Why? Khaled Harfoush 40 20  5/14/24 Details Let p be the probability of receiving a bit in error (1-p) is the probability of receiving a bit correctly Let n be a frame size (in bits) The probability of receiving a frame correctly (1-p)n For p=10-4 n (bits) Probability of no error 12,144 0.2968 4,048 0.667 Khaled Harfoush 41 So § 802.11 provides the possibility of fragmenting frames into fragments. Each transmitted as a separate frame – Individually numbered and ACK’ed. The fragment size is an 802.11 parameter Khaled Harfoush 42 21  5/14/24 2. Power Saving § The idea is to have the AP buffer traffic for STAs in power-save mode § Relies on Beacon frames sent by the AP periodically § Beacon frames include: 1. ID of the AP 2. Time 3. System parameters 4. Security settings 5. Map of STAs for which the AP has buffered traffic Khaled Harfoush 43 Power Saving Mechanisms § There a few possible mechanisms. Two most popular 1. Mechanism 1: Relies on Poll messages sent from a STA to AP 2. Mechanism 2: Does not use Poll messages § Clients set a power management bit in frames that they send to the AP to tell they are entering power-save mode Khaled Harfoush 44 22  5/14/24 Mechanism 1 1. The AP buffers traffic intended for the STA. 2. The AP periodically sends traffic map as part of the beacon frames 3. The STA in power-save mode wakes up periodically to listen to beacons 4. The traffic map tells the STA if it has buffered traffic. If so, it sends a poll message to the AP 5. The AP sends the traffic to the STA Khaled Harfoush 45 Mechanism 2 Automatic Power Save Delivery (APSD) 1. The AP buffers traffic intended for the STA. 2. When AP receives a frame from a STA with buffered traffic, it automatically transmits the traffic to the STA Khaled Harfoush 46 23  5/14/24 3. Quality of Service n Used to distinguish between different types of frames (control frames, VoIP, best effort, etc) n Different backoff slot times add quality of service -- Short intervals give preferred access n CSMA/CA still used Khaled Harfoush 47 802.11 Frame Structure n Frames vary depending on their type (Frame control) n Data frames have 3 addresses to pass via APs NAV fragmentation Khaled Harfoush 48 24  5/14/24 Next Lecture 1. Medium Access Control – More systems Khaled Harfoush 49 25