Multiple Access

Multiple Access Links

two types of “links”

  • Broadcast (shared wire or medium)

    • Old-school Ethernet

    • Upstream HFC in cable-based access network

    • 802.11 wireless LAN, 4G/4G. satellite

  • Point-to-Point

    • Point-to-point link between Ethernet switch, host

    • PPP for dial-up access

Multiple Access Protocols

  • Single shared broadcast channel

  • Two or more simultaneous transmissions by nodes - interference

    • Collision if node receives two or more signals at the same time

  • Distributed algorithm determine how nodes share channel, i.e., determine when node can transmit

  • Communication about channel sharing must use channel itself

    • No out-of-band channel for coordination

MAC Protocols

MAC - multiple access channel
3 broad classes

  • Channel partitioning

    • Divide channel into smaller “pieces” (time slots, frequency, code)

    • Allocate piece to node for exclusive use

  • Random access

    • Channel not divided, allow collisions

    • “Recover” from collisions

  • “Taking turns”

    • Nodes take turns, but nodes with more to send can take longer turns

Channel Partitioning MAC Protocols

TDMA - time division multiple access

  • Access to channel in “rounds”

  • Each station gets fixed length slot (length = packet transmission time) in each round

  • Unused slots go idle

  • Example - 6-station LAN, 1,3,4 have packets to send, slots 2,5,6 idle

FDMA -  frequency division multiple access

  • Channel spectrum divided into frequency bands

  • Each station assigned fixed frequency band

  • Unused transmission time in frequency bands go idle

  • Example - 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle

Random Access Protocols

  • When node has packet to send

    • Transmit at full channel data rate R

    • No a priori coordination among nodes

  • 2 or more transmitting nodes: “collision”

  • Random access protocol specifies:

    • How to detect collisions

    • How to recover from collisions (e.g., via delayed retransmissions)

  • Examples of random access MAC protocols - ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA

CSMA - carrier sense multiple access

  • simple CSMA: listen before transmit:

    • If channel sensed idle - transmit entire frame

    • If channel sensed busy - defer transmission

Collisions

  • Collisions can still occur with carrier sensing:

    • Propagation delay means two nodes may not hear each other’s just-started transmission

  • Collision - entire packet transmission time wasted

    • Distance & propagation delay play role in in determining collision probability

CSMA/CD - CSMA with collision detection

  • Reduces the amount of time wasted in collisions

  • Transmission aborted on collision detection

  • Collisions detected within short time

    • Colliding transmissions aborted, reducing channel wastage

    • Collision detection easy in wired, difficult with wireless

Ethernet CSMA/CD Algorithm

  1. Ethernet receives datagram from network layer, creates frame

  2. If Ethernet senses channel:

    • If idle: start frame transmission.

    • If busy: wait until channel idle, then transmit

  3. If entire frame transmitted without collision - done!

  4. If another transmission detected while sending: abort, send jam signal

  5. After aborting, enter binary (exponential) backoff:

    • After mth collision, chooses K at random from {0,1,2, …, 2m-1}. Ethernet waits K·512 bit times, returns to Step 2

    • More collisions: longer backoff interval

Slotted ALOHA

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

Operation

  • When node obtains fresh frame, transmits in next slot

  • If no collision - node can send new frame in next slot

  • If collision - node retransmits frame in each subsequent slot with probability p until success

Pros

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

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

  • Simple

Cons

  • Collisions, wasting slots

  • Idle slots

  • Nodes may be able to detect collision in less than time to transmit packet

  • Clock synchronization

Efficiency

  • Long-run fraction of successful slots (many nodes, all with many frames to send)

  • Suppose - N nodes with many frames to send, each transmits in slot with

  • probability p

    • Prob that given node has success in a slot = p(1-p)N-1

    • Prob that any node has a success = Np(1-p)N-1

    • Max efficiency - find p* that maximizes Np(1-p)N-1

    • For many nodes, take limit of Np(1-p)N-1 as N goes to infinity, gives

      • Max efficiency = 1/e = .37

  • At best - channel used for useful transmissions 37% of time!

MAC Addresses

  • 32-bit IP address

    • Network-layer address for interface

    • Used for layer 3 (network layer) forwarding

    • e.g.: 128.119.40.136

  • MAC (or LAN or physical or Ethernet) address

    • Function - used “locally” to get frame from one interface to another physically-connected interface (same subnet, in IP-addressing sense)

    • 48-bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable

    • e.g.: 1A-2F-BB-76-09-AD

      • Hexadecimal (base 16) notation (each “numeral” represents 4 bits)

  • Each interface on LAN

    • Has unique 48-bit MAC address

    • Has a locally unique 32-bit IP address (as we’ve seen)

    • Special broadcast MAC address FF:FF:FF:FF:FF, all hosts receive the packet

ARP - Address Resolution Protocol

ARP table - each IP node (host, router) on LAN has table

  • IP/MAC address mappings for some LAN nodes

    •  < IP address; MAC address; TTL>

  • TTL (Time To Live) - time after which address mapping will be forgotten (typically 20 min)