Computer Networking Lecture Notes

30 October 2012 • 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.
• Demultiplexing reverses multiplexing.

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 12 \(\mu\)sec.
  • The MAC protocol determines what goes when.
• Each sender gets channel access once every 12N \(\mu\)sec.

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

• 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.

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?

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 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)
    while true
      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)
    while true
      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.

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.

CSMA Protocols

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.
• Starting addresses have priority over ending addresses.
• Starting addresses can starve ending addresses.
• 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.