Notes - Multiple Access Protocol

ALOHA

• connect users in Hawaii, unable to do this below pacific ocean
• short range radio, ALOHA system

Pure ALOHA

• let users transmit when they have data
• Senders need to be able to sense if collisions occur
• multiple users share a common channel, contention systems
• if first fram overlaps another frame, checksums will be destroyed
• efficiency of ALOHA channel?
• users in 2 states
• typing or waiting
• frame time is the amount of time needed to transmit standard fixed length frame
• modeling
• Poisson distribution, mean N frames per frame time
• stations generate retransmissions of collision frames
• Throughput S is the offered load G times the probability P of a transmission succeeding S=GP

• In pure aloha there are no slots or timezones, so its possible to send at any time and cause a collision

Slotted Aloha

• slotted ALOHA, doubles the capacity of an ALOHA system
• station not permitted to send whenever user types a line, required to wait for the next "slot" or pre designated timeframe where users can send
• doubles throughput

• small increases in G can dramatically reduce performance as shown by the following dependence
• probability of transmission is

• expected number of transmissions is

Carrier Sense Multiple Access Protocols

• best channel utilization is 1/e for slotted ALOHA
• increase this by using carrier sense protocols
• Persistent and Non-persistent CSMA
• 1-persistent CSMA(Carrier Sense Multiple Access)
• Station has data to send listens to channel then if idle it will send data if not it waits until idle
• if collision occurs, wait a random amount of time and restart
• Propagation delay has an effect in sending, idle channel sensing does not account for the time it takes for the signal to get there to be sent
• bandwidth-delay product of the channel, if only tiny fraction of frame
• Non persistent CSMA
• conscious attempt to be less greedy
• station senses channel if free or not
• if channel is in use, does not continually sense, waits a random period of time before resending rather than waiting for exact time to send
• reduces amount of second tier collisions
• P-Persistent CSMA
• when station ready to send, senses channels, if idle transmits with probability p, if it doesn't transmit it defers
• "pretend collisions" inherent to sending
• CSMA with Collision Detection
• Persistent and non persistent CSMA protocols improve ALOHA
• CSMA/CD (CSMDA with Collision Detection)
• basis of Ethernet LAN
• CD is an analog process, listen to channel while transmitting, if signal read back is different from output signal, collision is occurring
• frame divided as shown in the figure below

• worst case scenario contention can occur unless the slot width is 2 times the length of the packet to be sent

Collision Free Protocols

• collisions can still occur during contention period, but not once station has captured the channel
• some protocols have no chance of collision
• A Bit-Map Protocol
• each contention period consists of N slots
• if station 0 has frame, it sends 1 bit to slot 0, no other station is allowed to send in this slot
• if station j, wants to send, it inserts a bit into slot j, then transmits frames in numerical order, since all agree on when something is sent, no collisions

• is a Reservation protocol
• reserves channel ownership in advance
• channel efficiency at low load easy to compute
• overhead per frame is N bits, amount of data is d bits
• efficiency = d/(d+N)
• at high load, d/(d+1) all stations have something to send all the time
• mean delay for frame is sum of time it queues + (N-1)d +N after being at the head of the internal queue
• Token Passing
• pass a small message called a token from one station to the next in a predefined order
• token is permission to send, if it has token it can send, if no queue it passes token
• token ring protocol
• topology of the network is a ring
• direction of transmission one way, in the same direction of token
• to stop frame, station needs to remove from ring
• physically might be connected in a bus, or in a line, called token bus but same principle
• performance is similar to bit map, token does not need to propagate to all stations before protocol advances to next step
• popular as an alternative to classic Ethernet
• FDDI(Fiber Distributed Data Interface)
• faster token ring created in 1990s
• RPR(Resilient Packet Ring)
• defined as IEEE 802.17
• metropolitan area networks
• Binary Countdown
• binary station addresses with a channel that combines transmissions
• channel broadcasts its address as binary bit string, all addresses same length
• as soon as station sees higher order bit position, it gives up
• this way whenever higher number stations want to send they get to send first

• efficiency is d/(d + log₂N) but if frame format is chosen so that sender's address is the first field of the frame, then we have 100% efficiency

Limited-Contention Protocols

• two strategies for channel acquisition
• rated with how well it deals with low and high load
• in general
• contention has low delay at low load since collisions are rare 
• collision free protocols have good efficiency at high load, but bad for low load since overhead is fixed
• goal would be to combine the two, limited-contention protocols
• contention protocols symmetric
• each station has chance to acquire channel, probability p
• system performance can be improved with asymmetry sometimes
• probability that one station transmits is kp(1-p)^k-1 and we find that the optimal value of p is 1/k if we differentiate that formula

• if we define small groups for the stations, we can keep the assignment close to the left edge of the graph, so that probability of success is higher
• The Adaptive Tree Walk Protocol
• based on the algorithm designed in the US Army for testing syphilis

• if collision occurs we only have to search once per level
• if q stations are distributed evenly, there will be 2^-iq stations below a specific node
•  this means that mean number of contending stations per slot is 1 at the level where 2^-iq = 1 so i = log₂q

Wireless LAN Protocols

• system of laptop computers that can communicate by radio
• example of broadcast channel
• office place with APs located around the building
• provides about 600 Mbps
• 802.11(WiFi)
• wireless LAN may not be able to transmit or receive frames from all other stations due to limited range
• each transmitter has some range
• hidden terminal problem
• CSMA is not as clear because if we listen for transmissions, they can still receive from transmitter outside of our range
• exposed terminal problem
• if we want to transmit at the same time, from two different regions, even though our networks may be independent, the range of the two may have some overlap, causes a false listen check
• MACA(Multiple Access with Collision Avoidance)
• basic idea sends a RTS(Request to Send)
• receiver replies with CTS(Clear to Send)
• after CTS received then its sends
• If RTS successfully reaches, the receiver broadcasts CTS so it silences the rest of the stations in range

Back to ToC