MAC sub layer

Note on 18 Jul 2002
MAC sub layer

• Medium Access Control sub layer
• Sub layer of Data Link layer
• Job is to control traffic on a multi-access channel

Channel Allocation Problem

• Static channel allocation
  • Simple - each user allocated a fixed amount of bandwidth
  • Provides good performance for few heavily loaded users
  • Doesn't work well with bursty traffic
  • Wastes bandwidth under normal use
• Dynamic channel allocation
  • Tries to reduce bandwidth wasteage by allocating bandwidth as it is needed
  • Complex

Dynamic channel assumptions

• Station model - The model consist of N stations. The probability of frame transmission is λΔt in a given time Δt. Stations block until frame has been successfully transmitted.
• Single channel assumption - there is only one channel for all communication
• Collision assumption - if two frames are transmitted simultaniously, the collide. All stations can detect collision
• Continuous time - frames can be transmitted at any time
• Slotted time - time is divided into discrete slots, and frames may only be tranmitted at start of slots
• Carrier sense - stations can tell if line is busy
• No carrier sense - stations cannot tell if line is busy

Types of dynamic channel allocation

• Contention
• Token Passing
• Slotted Access

Pure ALOHA

• Stations transmit whenever needed, collide frame will be destroyed, feedback broadcasting property, sender can know which frame collided
• Stations listen on channel and if collision occurs
  • Wait random length of time
  • retransmit frame
• Simple to implement
• Poor performance (best case is 18% channel utilisation)

Slotted ALOHA

• Discrete version of ALOHA
• One station maintains a heartbeat to mark time
• One time interval corresponds to one slot
• Stations may only transmit at the beginning of a slot
• More complex to implement than ALOHA & has problems if heartbeat fails
• Greater utilisation of banwidth (36%)

CSMA

• Carrier Sense Multiple Access Protocol
• Stations listen to channel first and only if channel is not busy do they transmit
• 3 main types >> protocols in which stations listen for a carrier & act accordingly
  1. 1-persistant
  2. nonpersistant
  3. p-persistant

1-persistant & nonpersistant

• 1-persistant
  1. sense channel
  2. if channel is idle then send frame else wait until channel is idle then send frame
  3. if collision then wait random time; goto 1 (main channel)
• nonpersistant
  1. sense channel
  2. if channel is idle then send frame else wait random time: goto 1
  3. if collision: then wait random time: goto 1

p-persistant

• p-persistant
  1. sense channel
  2. if channel is idle
     then
     with propability p send frame
     with probability q=1-p goto 1
     else wait random time; goto 1
  3. if collision
     then wait random time; goto 1

Performance

• 1 persistant - 50%
• 0.5 persistant - 70%
• 0.1 persistant - 90%
• nonpersistant - 90%
• 0.01 persistant - 99%

CSMA/CD

• Carrier Sense Multiple Access Protocol with Collision Detection
• Similar to CSMA except that stations stop transmitting the moment they detect a collision
• Collision detection is always analog process
• Also need to consider maximum contention period

Ethernet

• One implementation of the IEEE 802.3 standard
• IEEE 802.3 standard defines a 1-persistant CSMA/CD LAN
• Specifies requirements for various cables at various speeds
• Speeds vary from 1Mbps to 1Gbps

Ethernet types

Name	Cable	Max. Segment	Nodes/Seg	Advantages
10Base5	Thick Coax	500m	100	Good for backbones
10Base2	Thin Coax	200m	30	Cheapest
10Base-T	UTP	100m	1024	Easy installation/maintenance
10Base-F	Fibre	100m	1024	Good between building, poor price/ performance ratio
Fast Ether (100Mbps)	UTP/Coax/Fibre	100m Coax/UTP 2000m Fibre	varies	Good speed/ price compromise
Gigabit Ether (1000Mbps)	UTP/Coax/Fibre	100m Coax/UTP 2000m Fibre	varies	Fastest

Ethernet frame format
Binary Exponential Backoff Algorithm

• Ether uses Binary Exponential Backoff Algorithm to improve performance.
• Algorithm works as follows
  1. i:=0;
  2. if collision then
     1. wait random(2i)
     2. restransmit
     3. if collision then
        • If i < 1023 then i:=1+1;
        • goto 2.1

Slotted

• If t (time to detect collision) is long and frame are relatively short (as is often the case in fibre), then collisions are a major problem.
• Slotted protocols allow stations to transmit only at certain times or in a certain order, therefore no collisions
• Slotted protocols assume that if there are N stations then each station has a unique address from 0 to N-1

Bit map protocols

• Each contention period is broken into N slots
• At the start of each contention period -
  • If station 0 wishes to send, then it transmits a bit in the 0_th slot
  • If station 1 wishes to send, then it transmits a bit in the 1_st slot
  • If station j wishes to send, then it transmits abit in the l_th slot
• Each station (starting at 0), transmits in turn
• After all stations have transmitted a new contention period starts

Binary countdown

• If a station wants to send, it broadcasts it's binary id, starting with high order bit
• Id bits are OR'd together
• as soon as a station sees a high order bit that is 0 in it's address but has been overwritten with a 1 it gives up
• Careful choosing of the fraame structure can mean that this information is not wasted
• However, stations with low numbers can be starved

Token Passing

• Similar in idea to slotted access, but a token is passed round to indicate who can go next.
• Need to consider lost or damaged tokens
• Need to consider how to join 'ring'

Token bus 

• IEEE 802.4 standard
• Developed by General Motors
• Conceptually rings are good (known bounds)
• Physical rings are bad (easily broken)
• Token is used to implement logical ring on physical bus
• 4 priority classes are used to give guarantee for bandwidth

Token maintanance - Token Bus

• Ring creation - 1st station sends CLAIM_TOKEN frame and when it get's no response, creates a token and ring with itself.
• Station addition - periodically, the token holder broadcasts a SOLICIT_SUCCESSOR frame giving sender & sender's successors id. Stations with ids in that range may bid to join
• Station deletion - station X with successor S and predecessor P, leaves the ring by sending P a SET_SUCCESSOR token telling P that it's successor is now S.
• Lost Station
  • Station transmits token to successor
  • Station listens for token being passed or frame being sent
  • if neither occurs, token is passed again.
  • If token fails again, station transmits WHO_FOLLOWS
  • If failed stations successor see's WHO_FOLLOWS it responds using SET_SUCCESSOR
  • If WHO_FOLLOWS fails, station sends SOLICIT_SUCCESSOR_2 and ring is re-initialised
• Lost Token
  • each machine keeps timer
  • timer is reset everytime machine sees token
  • If timer reaches threshold - station issues CLAIM_TOKEN
• Multiple tokens
  • If station notices other transmission when it is holding token, it discards it's token

Token Ring

• IEEE 802.5 standard
• Developed by IBM
• Not really broadcast, but point to point
• Uses entirely digital technology
• Can run on virtually any transmission media
• Known upperbounds
• Important issue is "physical length of bit"

Token maintenance - Token Ring

• Token ring uses a monitor station to oversee the ring.
• Monitor station is responsible for seeing that token is not lost, for handling ring breakages, cleaning up after garbled frames and watching out for orphaned frames
• Any station must be able to become monitor
• Problems occur when there is problems with the monitor - a dead monitor can be replaced, but a sick monitor can cause havoc