Content

1. Ethernet
   1. Topology
   2. Frame Structure
   3. Multiple Access
2. WiFi
   1. Distributed Coordination Function (DCF)
      1. CSMA/CA (Collision Avoidance)
      2. CSMA/MACAW (Optional)
   2. Point Coordination Function (PCF)
3. Connecting Devices
   1. Repeater
      1. Hub
   2. Bridge/Switch
      1. Self-Learning

Ethernet

• Cheap
• Built-in PC component
• Continues to evolve
• Unreliable connectionless service

Topology

• Bus topology before mid-90s
  • Single collision domain
• Star topology - hub-based late 90s
  • Single collision domain
• Star topology - switch-based current
  • Each port connects to separate Ethernet segments -> not confined to single collision domain

Frame Structure

Bit-oriented protocol.

• Preamble: 8 B
  • 10101010 * 7 for clock sync
  • • 10101011 as sentinel
• Addresses: 6 B each
  • Higher 24 bits: manufacturer-specific
  • Broadcast: all 1s
  • NIC discards frames with mismatched destination address
• Type: 2 B
  • Protocol carried by (encapsulated in) this frame
  • Mostly IP, or others e.g. Novell IPX, ARP, Apple Talk
• CRC: 4 B
  • Address + type + payload
• Payload: 46 ~ 1500 B
  • NIC discards frames with improper length or failed CRC

Multiple Access

• CSMA/CD
  • Min frame size (preamble + header + payload + trailer = 72 B)
  • Transmit jam signal (48 bits) upon collision for others to have time to detect collision
• Binary exponential backoff
  • Avoid lockstep retransmission & adaptive retransmission
  • Steps
    • First collision: wait 0 or 1 slot time
      • 1 slot time = K = 512 bit transmission time
    • Second: wait {0,1,2,3} * K time units
    • Third: wait {0,1,...,7} * K time units
    • 10th or up: wait {0,1,...,2^10-1} * K time units
    • 16th: report failure to upper layer
• Minimum frame size
  • Worst case scenario
    • 2 farthest stations A & B on the same collision domain has propagation delay d_pg
    • A station needs at most 2 d_pg to detect collision
  • Due to the lack of an ACK scheme, a minimum frame size is needed to ensure collision can be detected before the transmission of a frame ends
  • 72 B = 576 bits
    • Max length is set to 2500 m -> 2 d_pg ~= 50 μs under transmission rate 10 Mbps -> 500 bits
  • Network speed increase
    • Decrease d_pg (distance)
    • Increase min frame size

WiFi

• Wireless LAN devices use radio frequencies
• Frame structure similar to Ethernet
  • Max payload can be 2312 B
• 2 modes of operation
  • Infrastructure network
    • Access points (AP) as gateway to internet
  • Ad hoc network
    • Temporary association of group of stations within range of each other
• CSMA/CD difficult
  • Signal too strong at transmitting NIC
  • Hidden station problem (HSP): not all stations can sense signals from each other

Distributed Coordination Function (DCF)

Contention service (best effort).

CSMA/CA (Collision Avoidance)

• If channel idle + DIFS, transmit
• If channel busy
  • Freezes timer, add random backoff time to countdown, resumes countdown when idle again
• If no ACK received, use binary exponential backoff algorithm and retries
• If has another frame to transmit, execute random backoff (same as channel busy)

CSMA/MACAW (Optional)

• Handshaking to reserve channel
  • Small request-to-send (RTS) frame shortens the collision waste time
  • Receive clear-to-send (CTS)
    • Broadcast to nearby nodes to avoid HSP
      • They adjust network allocation vector (NAV) to mark channel busy
  • Both frames carry duration info

Point Coordination Function (PCF)

Contentionless service (take-turns protocol).

Connecting Devices

Repeater

• Physical-layer device
• Acts on individual bits
• Regenerates original bit pattern to the other cable
• Bi-directional
• 2 segments connected by a repeater are 1 single network of the same collision domain

Hub

• Multiport repeater
• Bits coming in go out to all other links at the same rate

Bridge/Switch

• Link-layer device
• Store & forward
  • Examine frame header & selectively forward frame based on dest MAC
• CSMA/CD to access outgoing segment before transmission
  • Needs buffer
• Hosts usually have dedicated, direct link to switch
  • Each link is its own collision domain
• Advantages
  • Isolates collision domains
  • Simultaneous transmissions allowed
  • Transparent
    • No setup required
    • No modification of frames
  • Plug-and-play, self-learning
• Works fine if no redundant paths (cycles)

Self-Learning

Backward learning to build forwarding table.

• Frame arrives at port X from host P
  • Table for port X += P's MAC
• Forwarding decision
  • Frame arrives, destined to hosts in the same LAN (associated to the same port)
    • Discard
  • Frame arrives, entry found
    • Forward to that port
  • Frame arrives, unknown
    • Flood to all ports except the incoming one
• Dynamic topology
  • Frame arrives, entry found
    • Update timestamp
    • Purge all entries beyond aging time
  • Frame arrives, port number doesn't match with table
    • Update table

References

• Ethernet Minimum Frame Size