Computer Networking Lecture Notes

7 March 2013 • Shared Channel Medium Access

---

Outline

• Review
• Channels and shared resource management.
• A simple protocol.
  • Pure and slotted ALOHA.
• Collision management.
  • Persistence and carrier sense.
• Collision avoidance and reservations.
  • Bit maps, bit flags, and tokens.

Where We Are

End-Point Connectivity

• Point-to-point channels.

  

• Shared (multiaccess, broadcast, random access) channels.

  

Channels

• A channel can be point-to-point or shared.
  • Shared: broadcast, multi-access, random access.
• Point-to-point channels are (relatively) straightforward.
• Shared channels are more difficult to use.
  • And the differences between types is great.
• The medium-access control (MAC) sublayer of the data-link layer implements the sharing protocol.

Channel Allocation

• A classic shared resource problem:

  Share a channel among competing senders.

• A channel is a serially reusable resource for senders.
• One sender at a time, all receivers all the time.
  • For wired channels; wireless is slightly different.
• A bias towards wired channels over wireless.

Multiplexing

• Given N senders, do the obvious: divide the channel into N pieces.
  • This is known as multiplexing.
• Multiplexing can be done along any divisible channel characteristic.
  • Time and frequency are the usual characteristics.
  • Time in this lecture, time division multiplexing (TDM).
• Demultiplexing reverses multiplexing.

TDM Illustrated

TDM Timing Example

• It takes 12 \(\mu\)sec to put a 1,500 byte frame on a 1 Gb/sec network.
  • The frame time is 12 \(\mu\)sec.
• Give each sender exclusive access to the channel for the slot time ≥ the frame time.
  • The MAC protocol determines channel access order.
• Each of n senders gets one slot time exclusive channel access every n slot times.

Observations

• Multiplexing is simple, effective, and fair.
• Each sender experiences O(n) overhead.
• There’s a lot of global coordination.
  • Exclusive channel access.
  • Adjusting for changing N.
• Hosts with nothing to send waste their allocation.
  • Bursty traffic is ill-served.

Improvements

• Multiplexing is a static allocation policy.
  • Given N, assign channel divisions.
• A dynamic allocation policy would be more responsive.
  • The need to send data.
  • The number of senders on the channel.
• A more responsive allocation policy should provide more flexibility and efficiency.

A Simple Protocol

• Ugh, coordinated multiplexing is too complicated. Isn’t there a simpler way?
• A sender with a frame ready sends it.
  • No waiting, no asking, just send it.
• What happens when two senders have frames ready?

Collisions

• More than one frame on a (sub-)channel causes a collision.
  • Even if the overlap is one bit.
• Collision properties:
  • Collisions destroy packets.
  • Collisions are detectable.
  • Software (error detection) and hardware assure these properties.

Collision Recovery

• Senders involved in a collision have to retransmit.
• Each sender delays a random amount before retransmitting.
  • Avoid the obvious recollision.
  • This is random backoff.
• This protocols is known as pure ALOHA.
  • Collisions make pure ALOHA a contention protocol.

ALOHA

Analysis

• Let the frame time be ft.

  A successful sender s “reserves” the channel for 2ft.

• S accesses the channel for ft.
• Other hosts don’t access the channel for upto ft starting from t.

Results

Observations

• Pure ALOHA
  • doesn’t waste resources on idle senders.
  • doesn’t require coordination.
• However, collisions waste resources.
  • And random backoff introduces latency.
• How can this be improved?
  • Alas, anarchy is expensive.

Time

• Divide access into frame-time sized slots.
  • Hosts send only at slot beginnings.
  • This is slotted time, as opposed to continuous time.
• Contention only occurs at slot beginnings.
  • Contending hosts randomly backoff.
• This is the slotted ALOHA protocol.

Slotted ALOHA

Slotted Analysis

A successful sender s “reserves” the channel for ft.

• A host successfully accessing a slot has the whole slot without contention.
• Contention isn’t reduced, it’s just better organized.

Slotted Results

Slotted Observations

• Slotted ALOHA improves throughput, doubling the maximum.
  • The drop-off is still exponential.
• Managing contention is better than not managing it.
  • Assuming management overhead isn’t too great.
• How else can performance be improved?

Carrier Sense

• A useful general rule for contended resources is check before using.
  • If the resource is busy, come back later.
  • Avoid contention where possible.
• Carrier sense: hosts listen before sending.
  • Avoid the obvious collisions.
• Carrier sense multiple access (CSMA) protocols exploit this idea.

Persistence

• 1-persistent CSMA:

  send(frame)
    loop
      while channel busy
        skip
      transmit(frame)
      if not collision
        return
      wait random backoff
  

• 1-persistent: frame transmission on idle carrier with probability 1.

Persistence Collisions

• 1-persistence implicitly synchronizes waiting senders.

  

• Channel propagation can also cause hosts to send “at the same time.”

1-Persistent Results

Nonpersistence

• Nonpersistent CSMA: don’t be so eager to transmit.

  send(frame)
    loop
      while channel busy
        wait random backoff
      transmit(frame)
      if not collision
        return
      wait random backoff
  

• Nonpersistent CSMA provides better utilization at higher latency.

Nonpersistent Results

p-Persistence

• p-persistent CSMA uses slotted time.
• A sender flips a p-weighted coin at an idle slot start.
  • Heads: transmit.
  • Tails: wait until the next slot and try again.
• Collisions cause a random-backoff wait.
• p is a parameter trading throughput and delay.
• 802.11 MAC is based on p-persistent CSMA.

p-Persistent CSMA

CSMA Protocols

• CSMA protocols are a combination of several properties.

  

  • Each box represents a different CSMA protocol.
    • Not necessarily a useful protocol.

CSMA Collisions

• Despite listening before sending, CSMA protocols can cause collisions.
  • More than one ready host hears the network idle.
  • The hosts send their frames.
  • Crash!
• CSMA reduces collisions, it doesn’t eliminate them.
  • Is there anything to be done?

Collision Detection

• Some carrier-sense media allows listening while sending.
• Sensing a frame collide, a sender can stop immediately.
• Stopping early is called collision detection.
  • The protocol is called CSMA with collision detection (CSMA/CD).
• Old (classic) Ethernet used CSMA/CD.

Collision Timing

t1 = t2 t1 = A-to-B propagation delay ρ. t1 + t2 = A-to-B round-trip time.

ρ	=	100 m network / 2·109 m/sec
	=	0.5·10-7 sec
	=	50 nsec

Abandoning Collisions

• Is detecting and abandoning collisions useful?
  • Assume a 1 Gbit/sec NIC and a 40 byte = 320 bit frame.
  • The NIC transmits for at most 100 nsec before it detects a collision.
    • The NIC is around 1/3 of the way through a 40-byte frame before a collision arrives.
• Yes, it’s useful.

CSMA/CD Operation

• CSMA/CD operation has three phases: transmission, contention, and idle.

  

• Contention slots are at most 2t long.
  • t = end-to-end propagation time.
• CSMA/CD approximates slotted ALOHA with 2t slot size.

Collision Avoidance

• Collisions are inefficient. Can they be eliminated?
• Assumptions:
  • N hosts, addressed by 0 to N - 1.
  • Negligible propagation delay.
• The basic idea is to have two phases:
  1. Senders declare intention, are sorted out.
  2. Senders transmit according to phase 1 results.

Bit-Map Reservations

• The two phases of the bit-map protocol are
  1. Reservation: Hosts mark a bit-map frame indicating frames to send.
     • Hosts learn up-stream intentions.
  2. Transmission: Hosts with reservations transmit in increasing order by address.
• The bit-map protocol is an example of a reservation protocol.

Bit-Map Example

• N = 8.

Bit-Map Observations

• Lower-address hosts wait longer on average than do higher-address hosts.
  • But the overall average is N slot times.
• Protocol overhead is low even under low loads.
  • Assuming reservation frames are smaller than are data frames.
• Reservation frame length is O(n). Can it be made smaller?

Bit-Flag Reservations

• Use a one-bit reservation frame.
  1. Reservation: The first host to set the reservation-frame bit wins.
  2. Transmission: The winning host sends its data frame.
• This is a bit-flag protocol.

Bit-Flag Example

• N = 8.

Bit-Flag Observations

• Constant-size reservation frame.
• Low-address hosts have priority over high-address hosts.
• Low-address hosts can starve high-address hosts.
• Protocol overhead is low and independent of load.
• Constant size is good, but starvation is bad.
  • Can we do better?

Permissions

• Treat the reservation frame as a permission to transmit a packet.
  • The reservation frame is called a token.
  • A token has O(1) size.
• A host
  • receives the token,
  • sends a data frame, or not, and
  • sends the token to the next host.
• This is a token ring protocol (IEEE 802.5).

Token Example

• N = 8.

Observations

• Each host waits at most O(n) between sends.
• No host has priority over another host.
• Overhead is minimal and independent of load.
• A ring isn’t necessarily a physical feature.
  • Physical rings are more complex than buses.
• Token networks show up about once a decade.

Summary

• Shared channel complexity imposes data-link sublayers.
• Media access control (MAC) protocols implement channel sharing.
• ALOHA is a simple shouting protocol.
• Persistence and carrier sense protocols try to manage collisions.
• Reservation protocols try to avoid collisions.
• But despite everything, Ethernet wins.

---

This page last modified on 2012 November 13.