Channel Partitioning: tdma, fdma

Channel Partitioning: TDMA, FDMA

• Channel Partitioning: TDMA, FDMA

• divide channel into “pieces” (time slots, frequency)
• allocate piece to node for exclusive use

Packet Radio (PR) Access Technique:

• Packet Radio (PR) Access Technique:

• Users attempt to access a single channel in an uncoordinated or random manner

• Random Access: Aloha, Slotted Aloha

• allow collisions
• “recover” from collisions

• Random access MAC protocols

• efficient at low load: single node can fully utilize channel
• high load: collision overhead

Devised by Norman Abramson and his colleagues

• Devised by Norman Abramson and his colleagues

• University of Hawaii

• Simple, no synchronization

• when frame first arrives

• transmit immediately

• collision probability increases:

• frame sent at t0 collides with other frames sent in [t0-1,t0+1]

Assumptions:

• Assumptions:

• all frames same size

• time divided into equal size slots (time to transmit 1 frame)

• nodes start to transmit only slot beginning

• nodes are synchronized

• if 2 or more nodes transmit in slot, all nodes detect collision

Pros

• Pros

• single active node can continuously transmit at full rate of channel

• highly decentralized: only slots in nodes need to be in sync

• simple

Aloha protocols do not listen to the channel before transmission

• Aloha protocols do not listen to the channel before transmission

• Do not exploit info about other users

• Listening to the channel if any user is transmitting is key to the efficient wireless access

• This was the basic of CSMA protocols
• Carrier Sense Multiple Access Protocol

Two imp parameters in CSMA

• Two imp parameters in CSMA

• Detection delay
• Propagation delay

• Detection delay

• A function of the receiver hardware
• Time reqd for a terminal to sense whether or not the channel is idle

• Propagation delay

• Relative measure of how fast a packet travels from one station to another station (BS or AP)
• Systems must be built taking this parameter significantly in account
• High propagation delay impact efficiency
• E.g., two extreme transmitting users may get into collision again and again due to high propagation delay

1-persistent CSMA

• 1-persistent CSMA

• Listens to the channel, if idle transmit

• p-persistent CSMA

• Listens to the channel, if idle, transmit with prob p in the first slot or (1-p) in the next slot

• CSMA/CD

• Further improvement over earlier CSMA
• Not only listens to channel before transmissions but also during transmissions
• If collision is detected, transmissions are aborted immediately
• Saves valuable resources from wastage
• Combines “listen before talk” and “listen while talk”
• Happens in Ethernet (because of full-duplex radios)

The concept of CSMA/CD is interesting

• The concept of CSMA/CD is interesting

• How about applying it in wireless medium access control?

• Problems in wireless networks

• signal strength decreases proportional to the square of the distance
• the sender would apply CS and CD, but the collisions happen at the receiver
• a sender cannot “hear” the collision at the same time of transmission, because transmission power suppresses receiving power
• i.e., CD does not work
• furthermore, CS might not work if, e.g., a terminal is “hidden”

• Wireless MAC use variants of CSMA

• CSMA/CA (collision avoidance protocol)
• Does not make collision zero, just tries to reduce it
• Very popular in IEEE 802.11 (WLAN)

Station (STA)

• Station (STA)

• terminal with access mechanisms to the wireless medium and radio contact to the access point

• Basic Service Set (BSS)

• group of stations using the same radio frequency

• Access Point

• station integrated into the wireless LAN and the distribution system

• Portal

• bridge to other (wired) networks

• Distribution System

• interconnection network to form one logical network (ESS: Extended Service Set) based on several BSS

Direct communication within a limited range

• Direct communication within a limited range

• Station (STA): terminal with access mechanisms to the wireless medium
• Basic Service Set (BSS): group of stations in range and using the same radio frequency

• Access methods

• DCF CSMA/CA (mandatory)
• collision avoidance via exponential backoff
• Minimum distance (IFS) between consecutive packets
• ACK packet for acknowledgements (not for broadcasts)
• DCF with RTS/CTS (optional)
• Distributed Foundation Wireless MAC
• avoids hidden terminal problem
• PCF (optional)
• access point polls terminals according to a list

Priorities

• Priorities

• defined through different inter frame spaces
• SIFS (Short Inter Frame Spacing)
• highest priority, for ACK, CTS, polling response
• PIFS (PCF IFS)
• medium priority, for time-bounded service using PCF
• DIFS (DCF, Distributed Coordination Function IFS)
• lowest priority, for asynchronous data service, competing stations

Station ready to send

• Station ready to send

• starts sensing the medium (Carrier Sense)

• If the medium is free for the duration of an Inter-Frame Space (IFS), the station can start sending (IFS depends on service type)

• If the medium is busy, the station has to wait for a free IFS, then the station must additionally wait a random back-off time

• collision avoidance, multiple of slot-time

• If another station occupies the medium during the back-off time of the station, the back-off timer freezes

Sending unicast packets

• Sending unicast packets

• station has to wait for DIFS before sending data
• receivers acknowledge at once (after waiting for SIFS) if the packet was received correctly (CRC)
• automatic retransmission of data packets in case of transmission errors

When the other stations find the channel idle, they would like to transmit their own packets

• When the other stations find the channel idle, they would like to transmit their own packets

• Contention for channel

• If all the waiting stations attempt at once, this will surely result in collision

• Some CA scheme is necessary
• Backoff intervals can be used to reduce collision probability

When transmitting a packet, choose a backoff interval in the range [0,cw]

• When transmitting a packet, choose a backoff interval in the range [0,cw]

• cw is contention window

• Count down the backoff interval when medium is idle

• Count-down is suspended if medium becomes busy

• When backoff interval reaches 0, transmit packet

The time spent counting down backoff intervals is a part of MAC overhead

• The time spent counting down backoff intervals is a part of MAC overhead

• Choosing a large cw leads to large backoff intervals and can result in larger overhead
• Choosing a small cw leads to a larger number of collisions (when two nodes count down to 0 simultaneously)

• Since the number of nodes attempting to transmit simultaneously may change with time, some mechanism to manage contention is needed

• IEEE 802.11 DCF: contention window cw is chosen dynamically depending on collision occurrence
• Follows Binary exponential backoff algorithm

Even before the first collision, nodes follow BEB

• Even before the first collision, nodes follow BEB

• Initial backoff interval (before 1st collision)

• [0,7]

• If still packets collide, double the collision interval

• [0,15], [0,31] and so on…

• Express this binary exponential backoff interval as a function of collision number

Two nodes, A and C both waiting for a busy channel to be idle so that they can proceed with their first transmission. After the channel becomes idle, what is the probability of A and C colliding in their first transmissions?

• Two nodes, A and C both waiting for a busy channel to be idle so that they can proceed with their first transmission. After the channel becomes idle, what is the probability of A and C colliding in their first transmissions?

Two nodes, X and Y intend to transmit frames of 10 and 5 timeslots. Initially after waiting for DIFS, X and Y both generate random backoff number, rX and rY as 2. In the next stage, X generates rX =1 and Y generates rY =3. What will be the time (slots) taken to complete both transmissions and receive acks?

• Two nodes, X and Y intend to transmit frames of 10 and 5 timeslots. Initially after waiting for DIFS, X and Y both generate random backoff number, rX and rY as 2. In the next stage, X generates rX =1 and Y generates rY =3. What will be the time (slots) taken to complete both transmissions and receive acks?

• Assume, SIFS=1 timeslot, DIFS=2 timeslots

idea: allow sender to “reserve” channel rather than random access of data frames: avoid collisions of long data frames

• 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

• CTS heard by all nodes

• sender transmits data frame
• other stations defer transmissions

Sending unicast packets

• Sending unicast packets

• station can send RTS with reservation parameter after waiting for DIFS (reservation determines amount of time the data packet needs the medium)
• ack via CTS after SIFS by receiver (if ready to receive)
• sender can now send data at once, acknowledgement via ACK
• other stations store reservations distributed via RTS and CTS

All backlogged nodes choose a random number, R

• All backlogged nodes choose a random number, R

• Each node counts down R

• Continue carrier sensing while counting down
• Once carrier busy, freeze countdown

• Whoever reaches ZERO transmits RTS

• Neighbors freeze countdown, decode RTS
• RTS contains (CTS + DATA + ACK) duration = T_comm
• Neighbors set NAV = T_comm
• Remains silent for NAV time

Receiver replies with CTS

• Receiver replies with CTS

• Also contains (DATA + ACK) duration.
• Neighbors update NAV again

• Tx sends DATA, Rx acknowledges with ACK

• After ACK, everyone initiates remaining countdown
• Tx chooses new R = rand (0, CW)

• If RTS or DATA collides (i.e., no CTS/ACK returns)

• Indicates collision
• RTS chooses new random no. following BEB

Two nodes, X and Y intend to transmit frames of 10 and 5 timeslots. Initially after waiting for DIFS, X and Y both generate random backoff number, rX and rY as 2. In the next stage, X generates rX =1 and Y generates rY =3. What will be the time (slots) taken to complete both transmissions and receive acks?

• Two nodes, X and Y intend to transmit frames of 10 and 5 timeslots. Initially after waiting for DIFS, X and Y both generate random backoff number, rX and rY as 2. In the next stage, X generates rX =1 and Y generates rY =3. What will be the time (slots) taken to complete both transmissions and receive acks?

• Assume, SIFS=1 timeslot, DIFS=2 timeslots
• RTS threshold = 8.