Scribd Logo
Upload

Welcome to Scribd!

  • 398 views

    Wireless Medium Access Control Protocols: CS 851 Seminar University of Virginia

    Uploaded by

    kenjo138
    The document summarizes key aspects of the MACA and MACAW wireless medium access control protocols. MACA introduced a three-way handshake to reserve the wireless channel before data transmission, but did not fully address hidden and exposed terminal problems. MACAW refined MACA with a four-way handshake, added a five-way handshake to further address exposed terminals, and introduced request-to-send messages and backoff algorithms to improve fairness. It also proposed a multiple stream model to separate traffic from different flows for improved fairness compared to a single stream model.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Wireless Medium Access Control Protocols: CS 851 Seminar University of Virginia

    Uploaded by

    kenjo138
    398 views47 pages
    The document summarizes key aspects of the MACA and MACAW wireless medium access control protocols. MACA introduced a three-way handshake to reserve the wireless channel before data transmission, but did not fully address hidden and exposed terminal problems. MACAW refined MACA with a four-way handshake, added a five-way handshake to further address exposed terminals, and introduced request-to-send messages and backoff algorithms to improve fairness. It also proposed a multiple stream model to separate traffic from different flows for improved fairness compared to a single stream model.

    Original Description:

    Explanation on MAC MACA and MACAW

    Original Title

    Mac Maca Macaw

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes key aspects of the MACA and MACAW wireless medium access control protocols. MACA introduced a three-way handshake to reserve the wireless channel before data transmission, but did not fully address hidden and exposed terminal problems. MACAW refined MACA with a four-way handshake, added a five-way handshake to further address exposed terminals, and introduced request-to-send messages and backoff algorithms to improve fairness. It also proposed a multiple stream model to separate traffic from different flows for improved fairness compared to a single stream model.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    398 views47 pages

    Wireless Medium Access Control Protocols: CS 851 Seminar University of Virginia

    Uploaded by

    kenjo138
    The document summarizes key aspects of the MACA and MACAW wireless medium access control protocols. MACA introduced a three-way handshake to reserve the wireless channel before data transmission, but did not fully address hidden and exposed terminal problems. MACAW refined MACA with a four-way handshake, added a five-way handshake to further address exposed terminals, and introduced request-to-send messages and backoff algorithms to improve fairness. It also proposed a multiple stream model to separate traffic from different flows for improved fairness compared to a single stream model.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 47

    Wireless Medium Access Control

    Protocols
    CS 851 Seminar
    University of Virginia
    www.cs.virginia.edu/~cs851-2/course.html

    Why Need MAC ?

    Wireless medium is an open, shared, and broadcast medium


    Multiple nodes may access the medium at the same time
    A

    Medium Access Control Protocol:


    Define rules to force distributed nodes to access wireless medium in
    an orderly and efficiently manner
    2

    Ideal MAC Protocol

    Limited Delay
    High Throughput
    Fairness
    Stability
    Scalability
    Robustness against channel fading
    Low power consumption
    Support for multimedia

    Some Background

    CSMA/CD (carrier sense multiple access/ collision detection)


    Every node senses the carrier before transmitting
    If the carrier is not clear, the node defers transmission for a specified
    period. Otherwise, transmits
    While transmitting, the sender is listening to carrier and sender stops
    transmitting if collision has been detected

    Due to hidden & exposed terminal problem


    Contention/collision will occur at receiver side
    Carrier sense (send side) approach is inappropriate for wireless
    networks

    Wireless MAC Issues

    Half-Duplex Operation
    Time Varying Channel
    Burst Channel Errors
    Location Dependent Carrier Sensing
    Hidden Terminal
    Exposed Terminal
    Capture

    Hidden Terminal Problem

    Node B can communicate with A and C both


    A and C cannot hear each other
    When A transmits to B, C cannot detect the transmission
    using the carrier sense mechanism
    If C transmits to D, collision will occur at B

    Exposed Terminal Problem

    Node C can communicate with B and D both


    Node B can communicate with A and C
    Node A cannot hear C
    Node D can not hear B
    When C transmits to D, B detect the transmission using the
    carrier sense mechanism and postpone to transmit to A,
    even though such transmission will not cause collision

    D
    7

    Capture Effect
    Power
    Difference
    Of A and
    D signals

    D B

    A and D transmit simultaneously to B, the signal


    strength received by B from D is much higher than
    that from A, and Ds transmission can be decoded
    without errors. This will result unfair sharing of
    bandwidth.
    8

    Classification of Wireless MAC Protocols

    Wireless MAC Protocols

    Distributed Mac
    Protocols

    Random
    access

    Centralized MAC
    Protocols

    Guaranteed
    access

    Distributed MAC Protocols

    Collision avoidance mechanisms


    Collision avoidance with out-of-band signaling
    Collision avoidance with in-band control messages
    Two distributed random access protocols
    DFWMAC: Distributed Foundation Wireless MAC (used in IEEE

    802.11)
    EY-NPMA: Elimination Yield-Nonpreemptive Priority Multiple
    Access (used in HyperLan)

    10

    Centralized MAC Protocols

    Work for centralized wireless networks

    Base station has explicit control for who and when to access the
    medium

    All nodes can hear from and talk to base station


    All communications go through the base station

    The arbitration and complexity are in base station


    11

    MACA: A New Channel Access


    Method for Packet Radio
    Phil Karn 1990

    12

    Goals , New Ideas, and Main


    Contributions

    Goals:
    Try to overcome hidden & exposed terminal problems
    New idea:
    Reserve the channel before sending data packet
    Minimize the cost of collision (control packet is much smaller than
    data packet)

    Main Contribution:
    A three-way handshake MAC protocol : MACA

    CSMA/CA

    MA/CA

    MACA
    13

    Fundamental Assumptions

    Symmetry
    A can hear from B B can hear from A
    No capture
    No channel fading
    Packet error only due to collision
    Data packets and control packets are transmitted in the
    same channel

    14

    Three-Way Handshake

    A sends Ready-to-Send (RTS)


    B responds with Clear-to-Send (CTS)
    A sends DATA PACKET

    RTS and CTS announce the duration of the data transfer

    Nodes overhearing RTS keep quiet for some time to allow A to receive CTS

    Nodes overhearing CTS keep quiet for some time to allow B to receive data
    CTS (10)
    packet
    RTS (10)
    DATA
    CTS: Request
    Clear ToTo
    Send
    RTS:
    Send
    D
    B
    C

    A
    E
    15

    More Details for MACA

    A sends out RTS and set a timer and waits for CTS
    If A receives CTS before timer go to zero, OK! sends data packet
    Otherwise, A assumes there is a collision at B
    Double the backoff counter interval

    Randomly pick up a timer from [1,backoff counter]


    Send next RTS after timer go to zero

    B sends out CTS, then set a timer and waits for data packet
    If data packet arrives before timer go to zero, OK!
    Otherwise, B can do other things
    C overhears As RTS, set a timer which is long enough to allow A to receive
    CTS. After the timer goes to zero, C can do other things
    D overhears Bs CTS, set a timer which is long enough to allow B to receive
    data packet.
    E overhears As RTS and Bs CTS, set a timer which is long enough to allow B
    to receive data packet.
    RTS and CTS can also contain info to allow sender A to adjust power to reduce
    interference

    Note: no carrier sense

    16

    Hidden Terminal Problem Still Exists (1)


    Data

    packet still might suffer collision

    DATA
    RTS

    RTS

    CTS

    17

    Hidden Terminal Problem Still Exists (2)


    Data

    packet still might suffer collision

    DA
    R
    CTTA

    CTS
    RTS
    DATA
    RTS

    B
    A

    18

    Exposed Terminal Problem Still Exists


    Node

    C can not receive CTS


    RTS
    DATA
    CTS
    RTS
    CTS
    B

    19

    Summary

    MACA did not solve hidden & exposed terminal problems


    MACA did not provide specifications about parameters
    What are RTS, CTS packet sizes ?
    How to decide timers?
    What is initial backoff window size?
    A lot things need to do if using MACA

    20

    MACAW: A Media Access Protocol


    for Wireless Lans
    V. Bharghavan, A. Demers, S. Shenker, and L. Zhang (Sigcomm 1994)

    21

    Goals, New Ideas, and Main


    Contributions

    Goals:
    This paper refined and extended MACA

    New Idea: Information sharing to achieve fairness


    Main Results:
    Modified control messages
    Four-way handshake (reliable, recover at MAC layer)
    Five-way handshake (relieve exposed terminal problem)
    RRTS (unfairness)
    Modified back-off algorithms
    Multiplicative increase and linear decrease (MILD)
    Synchronize back-off counter using piggyback message
    Multiple stream model (V-MAC)

    22

    Revisit Hidden Terminal Problem

    Data packet still may suffer collision


    To recover packet loss at transport layer is too slow
    Recover at MAC layer is more fast
    Need ACK from destination

    23

    Four-Way Handshake

    Sender sends Ready-to-Send (RTS)


    Receiver responds with Clear-to-Send (CTS)
    Sender sends DATA PACKET
    Receiver acknowledge with ACK
    RTS and CTS announce the duration of the transfer
    Nodes overhearing RTS/CTS keep quiet for that duration
    Sender will retransmit RTS if no ACK is received
    If ACK is sent out, but not received by sender, after receiving new RTS, receiver returns ACK instead of
    CTS for new RTS

    CTS: Request
    Clear ToTo
    Send
    RTS:
    Send

    RTS(T)
    DATA

    CTS(T)
    ACK

    destination
    source

    24

    Comparison with ACK and without ACK

    25

    Revisit Exposed Terminal Problem

    RTS/CTS/DATA/ACK can not solve exposed terminal


    problem
    When overhearing RTS, the node needs to wait longer
    enough to allow the data packet being completely
    transmitted even it does not overhear CTS
    To relieve exposed terminal problem,
    Let exposed terminal know the DATA packet does be transmitted
    Extra message DS (data send)
    Five Handshaking to let exposed terminal know how long
    it should wait
    26

    Five-Way Handshake

    Sender sends Ready-to-Send (RTS)


    Receiver responds with Clear-to-Send (CTS)
    Sender sends DATA SENDING (DS)
    Sender sends DATA PACKET
    Receiver acknowledge with ACK
    RTS and CTS announce the duration of the
    transfer
    Nodes overhearing RTS/CTS keep quiet for that
    duration

    CTS:
    Clear
    ToTo
    Send
    RTS:
    DS:Request
    Data Sending
    Send

    DATA
    RTS
    DS

    CTS
    ACK

    A
    27

    Comparison with DS and without DS

    28

    Comparison with DS and without DS

    CT
    R
    TS
    S

    CTS
    ACK
    DATA
    RTS

    P1

    P2

    B2

    B1

    29

    Unfairness

    Using RTS/CTS/DATA/ACK or RTS/CTS/DS/DATA/ACK might cause unfairness


    A sends data to B; D sends data to C
    A and D have enough data to send
    C can hears from B and D, but not A
    B can hear from A and C, but not D
    A is in luck and gets the channel
    D sends RTS and times out
    Backoff window for D repeatedly doubles
    For the next transmission:
    A picks a random number from a smaller window
    Unequal probability of channel access
    Throughput for flow A B > 90 %
    RTS
    Throughput for flow D C ~ 0%

    DATA
    RTS

    CTS
    ACK

    B
    A

    30

    Request for RTS (RRTS)

    Try to solve unfairness by having C do the contending for D

    RRTS: Request for RTS

    DATA
    RTS

    RTS
    RR
    TS

    ACK
    CTS

    B
    A

    31

    Why Uses RRTS Instead Of CTS ?

    CTS or RTS packet size << data packet size

    When nodes overhear CTS, they need to defer a time


    period to allow the expected data packet transmission

    When nodes overhear RRTS, they only need to defer a


    time period to overhear the expected CTS

    Uses CTS will cost long waiting

    32

    Comparison with RRTS and without RRTS (1)

    33

    Comparison with RRTS and without RRTS (2)

    34

    Multiple Stream Model (V-MAC)


    MAC

    MAC

    Node

    Single Stream MAC

    MAC
    MAC

    Node

    Multiple Stream MAC

    Single stream model merges traffic from different flows into a mixed
    stream and uses a single MAC
    Multiple stream model uses multiple MAC (one flow one MAC) to
    achieve fairness
    This idea was used by Intersil
    for IEEE 802.11e in 2001

    Company to propose a new MAC


    35

    Why Multiple Stream MAC more fair Than Single


    Stream MAC

    When collision

    all packets in single stream MAC are used a large backoff window
    Different flows packet in multiple stream MAC uses different
    backoff window

    36

    Comparison V-MAC and MAC

    37

    Backoff Algorithms

    When collision occurs, node A pick up a random number T from


    [1,Bo], then retransmits RTS after T time unit

    How to determine Bo
    After each collision Bo_new = Fun_inc(Bo_old)
    After each successful transmission Bo_new = Fun_dec(Bo_old)

    Binary exponential backoff (BEB) algorithm


    Fun_inc(Bo_old)=min{2*Bo_old, Bo_max}
    Fun_dec(B_old)=Bo_min

    Multiplicative increase linear decease (MILD)


    Fun_inc(Bo_old)=min{1.5*Bo_old, Bo_max}
    Fun_dec(B_old)=max{Bo_old -1, Bo_min}

    38

    Information Sharing in Backoff


    Algorithms

    When a node sends a packet, it embeds its current backoff


    counter in the packet header. Other nodes which overhears the
    packet copy the value as itself backoff counter

    Key idea: all nodes have the same backoff counter to achieve
    fairness

    39

    Comparison BEB and BEB-Copy

    40

    Comparison BEB-COPY and MILD-Copy

    41

    Per-Destination Backoff

    42

    Evaluation of MACAW

    43

    Evaluation of MACAW
    Every flow has the
    same data rate
    32 packet per second

    Total Troughput
    MACA: 51.06
    MACAW: 70
    37% higher

    44

    Evaluation of MACAW

    45

    Evaluation of MACAW

    46

    Open Problems

    How to design a good backoff algorithm?

    Adaptive MAC to achieve fairness in ad-hoc networks

    Do upper layer operations need to tightly relate to MAC?

    Reliable multicast MAC in ad-hoc networks

    47

    You might also like