The Medium Access Control Sublayer

The Medium Access Control Sublayer

Chapter 4

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Channel Allocation Problem

? Static channel allocation

FDM/TDM

? Assumptions for dynamic channel allocation

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Assumptions for Dynamic Channel Allocation

1. Independent traffic: independent stations 2. Single channel: available for all communication. All

stations can transmit/receive on/from it. The stations are equally capable. 3. Observable Collisions: All stations can detect a collision. 4. Continuous or slotted time (for transmission) 5. Carrier sense or no carrier sense: With carrier sense, stations can tell if the channel is in use before trying to use it.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Multiple Access Protocols

? ALOHA: Early 1970s.

Pure Aloha Slotted Aloha

? Carrier Sense Multiple Access ? Collision-free protocols ? Limited-contention protocols ? Wireless LAN protocols

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

ALOHA

Basic idea of ALOHA: let users transmit whenever they have data to be sent.

Collisions are possible! Sender might be able to listen for collisions while transmitting If the frame was destroyed, the sender just waits a random

amount of time to retransmit it.

The waiting time must be random or the frames will collide again.

Contention systems: Systems in which multiple users share a common channel in a way that can lead to conflicts.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

ALOHA (1)

User A B C D E

Collision

Time

Collision

In pure ALOHA, frames are transmitted at completely arbitrary times

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

ALOHA (2)

Vulnerable period for the shaded frame.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

ALOHA (3)

(Including retransmission)

Throughput versus offered traffic for ALOHA systems.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Slotted Aloha

Divide time into discrete intervals called slots, each interval corresponding to one frame.

Require the users to agree on slot boundaries A station is not permit to send at any time. It is required to

wait for the beginning of the next slot

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Carrier Sense Multiple Access Protocol

When a station has data to send, it first listens to the channel to see if anyone else is transmitting.

If the channel is idle, the station sends data. Otherwise, it just waits until it become idle.

If a collision occurs, the station waits a random amount of time and starts all over again.

1-persistent: the station transmits with a probability of 1 when it finds the channel idle.

p-persistent: the station transmits with a probability of p when it finds the channel idle.

Non-persistent CSMA: If the channel is already in use, the station does not continuously sense the channel for the purpose of seizing it immediately upon detecting the end of the previous transmission. Instead, it waits a random period of time and then repeats the algorithm.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Persistent and Nonpersistent CSMA

Comparison of the channel utilization versus load for various random access protocols.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

CSMA with Collision Detection

The stations quickly detect the collision and abruptly stop transmitting (rather than finishing them).

Saves time and bandwidth. CSMA/CD (Collision Detection): basis of the classic Ethernet The station hardware must listen to the channel while it is

transmitting. A received signal must not be tiny compared to the transmitted signal (for reading back transmitting data). Chose appropriate modulation method to allow collisions to be detected.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

CSMA with Collision Detection

CSMA/CD can be in one of three states: contention, transmission, or idle.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Collision-Free Protocols (1)

Each contention period consists of exactly N slots. If station 0 has a frame to send, it transmits a 1 bit during slot 0. No other station is allowed to transmit during this slot.

Each station has complete knowledge of which stations wish to transmit.

After the last station has transmitted its frame, another N-bit contention period is begun.

Reservation protocol

The basic bit-map protocol

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Collision-Free Protocols (2)

Token: A small message representing permission to send

If a station has a frame queued for transmission when it

receives the token, it can send that frame before it passes

the token to the next station. The network topology defines the order in which stations

send.

Token Bus: We do not need a physical ring to implement token

passing. Station

Token

Direction of transmission

Token ring

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

Binary Countdown

Scaling problem: One bit per station for basic bit-map protocol

A station wanting to use the channel broadcasts its address as a binary bit string with the high-order bit.

The bits in each address position from different stations are ORed together when they are sent. Higher-numbered stations have a higher priority than low-numbered stations

The binary countdown protocol. A dash indicates silence.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, ? Pearson Education-Prentice Hall, 2011

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download