CS144 7-5 CSMA/CD and Ethernet

Introduction to Computer Networking, Stanford University
https://lagunita.stanford.edu/courses/Engineering/Networking-SP/SelfPaced/about

Introduction to Computer Networking

Unit 7: Lower Layers 중 CSMA/CD and Ethernet 파트 수업 필기 정리

 

---

 

 

0. Intro

• Ethernet is the most widely used mechanism in the internet
• Link Layer covers:
• how an end host is connected to a router
• how one router is connected to the next
• Packets and IP layer are encapsulated into a linked layer frame (most often ethernet) to be sent off to the first router
• CSMA/CD is the core of how Ethernet works
• Ethernet switching became a very common way to extend the scope of a link to cover many end hosts connected to a single router

 

1. Why is Ethernet often referred to as "Layer 2" ?

• Link Layer(Ethernet) is the lowest layer in Internet Model,
  and the layer 2 in OSI Model
• Link Layer covers the frame format the algorithm,
  that decides when a packet can be sent onto the wire
  → this is CSMA/CD mechanism
• Physical Layer covers connectors and the electrical signals used on the wire

 

2. The Origins of Ethernet

• ethernet started out as a means to connect multiple computers together on a single cable (a long string, a long bus)
• computers are all sharing access to the same common wire
• but only one packet is allowed onto the cable at a time to prevent collision, corruption or interference

 

3. Sharing a "medium"

• Ethernet is an example of multiple hosts sharing a common cable(the "medium")
• to share the medium, we need to decide who gets to send and when and who is the next?
• there's a general class of "Medium Access Control Protocols" (MAC protocols):
  → algorithms to decide who gets to send next
  • Ethernet addresses often referred to as MAC address
    → even though Ethernet doesn't use this mechanism any more! just a vestige of the earlier 10MB per second of Ethernet :P

 

4. Examples of MAC Protocols

• Aloha:
  the simplest protocol
  • Random Access Protocol:
    every host tries to send data at any time, so it's random
  • but when heavy load, packets collides, corrupts each other until they gets to send
• Token Passing:
  most common method of deterministic protocols
  • Deterministic protocols:
    explicitly controls who gets to send a packet next
  • Token here is like a permit to send a packet,
    so when host gets a tocken, send a packet, and pass the token
  • hosts are connected on a ring, so the token will go around
  • every hosts gets the chance to send a packet in a deterministic order
  • it requires to generate and maintain the token,
    so easy to fail: have been replaced by Ethernet
• Ethernet:
  Carrier Sense Multiple Access/Collision Detection (CSMA/CD)
  every hosts just basically randomly sends

 

5. Goals of MAC protocols

Medium Access Control protocols arbitrate중재 access to a common shared channel among a population of users

1. High utilization of the shared channel:
   prevent collision ... etc
2. Fair use of the channel among end hosts:
   Equal opportunities to send packets averaged over a long period
3. Simple and low cost to implement:
   so it can be widely deployed
4. Robust to errors; fault tolerent

 

6. Examples

1) Aloha Network(1968)

• one of the earliest MAC protocols used in Aloha Network in Hawaii
• a central station in Oahu(where Honolulu is),
  and radio transmitters are on other islands around it
• every packets was sent to the central station,
  and re-broadcasted out to everybody
• so the medium here was air

• The way it works:

  

  1. hosts send packets on Frequency 0
  2. the packet data is retransmitted out over Frequency 1, a separate frequency
• Original Aloha MAC protocol
  1. if you have data to send, transmit it
  2. if your transmission "collides" with another, retry later:
     → you listen on frequency 1, then if what came back was not a correct copy of what you sent, then it must have collided

• features

  • Aloha protocol is very simple
  • quite robust against failure of a host:
    when a host fails and stops, the central is not affected by it
  • The protocol is distributed among the hosts:
    every host operates independently
  • Under low-load: small delay
  • Under high-load: lots of time "wasted" sending packets that collided
    → Improving performance
    1. Listen for activity, before sending a packet
       → "Carrier Sense"
    2. Detect collisions quickly and stop transmitting
    3. After collision, pick random waiting time based on the load (high load: wait a long time)

2) CSMA/CD Protocol

this is what was used for the original 10Megabit per second Ethernet.
→ all hosts can transmit and receive on the one channel(the wire, shared medium)

When a host has a packet to transmit:

1. Carrier Sense:
   Check the line is quiet for before transmitting,
   Send the packet,
   Listen for the collision,
2. Collision Detection:
   Detect collision ASAP
   If a collision is detected, stop transmitting.
   wait a random time, then return to step 1.
   • random time: binary exponential backoff
     if there are lots of collisions = lots of other transmitters, then wait a longer time to give every host equal opportunity to send packets

Operation in Practice

• in order for a host to realize that there was a collision and stop transmitting, back off, then retransmit,
• sending a packet for at least 2L/C (L = length of the cable, C is speed of light) seconds:
  L/C when started and then another L/C until small bit of packet from the other side reach the starting point, in the worst case
• P/R(packet length divided by rate) ≥ 2L/C
  P ≥ R*2L/C
  (P= packet length, R= bit per second)

Example of Packet Size Requirement

• when R = 10MB/s, L = 10000m
  then P ≥ 10⁷ * ( 2 * 10⁴) / (2 * 10⁸) = 1000 bits
• CSMA/CD network to operate correctly in this situation,
  the minimum size of packet has to be a 1000 bits or about 128 bytes!

 

---

Problem Set

 

Problem 7-5A

You are considering two retransmission strategies for all hosts in a network using the ALOHA protocol. The first is a deterministic strategy where the first time a collision is detected, the sender waits one second and retransmits. The second time a collision is detected, the sender waits two seconds and retransmits, and so on. The second strategy is a random strategy where when a collision is detected, the sender waits a random amount of time and retransmits. After the first collision it randomly chooses between waiting 0 or 1 seconds; after the second collision it randomly waits between 0 and 2 seconds, and so on.

The answers are:

• The random strategy will perform better under high-load correct
• The deterministic strategy will not recover from collisions correct

Explanation

In the deterministic strategy, when a collision occurs both senders will backoff for 1 second. Then they will try to resend and collide again, so they will backoff for 2 seconds. They will continue to collide like this forever. This strategy will not work, but the random one will.

 

Problem 7-5B

In a CSMA/CD network, the end hosts are upgraded from 10Mb/s to 100Mb/s. The size and layout of the physical network otherwise remains the same. Which of the following are true?

The answers are:

• The minimum packet size should be made ten times larger.
• The amount of time a packet spends on the wire is decreased by 10 times.
  (잘게 쪼개 보내던 것을 더 큰 덩어리로 쪼개 보내니까)

Explanation

For CSMA/CD to work, a packet needs to be on the wire for long enough to detect collisions. Because the amount of time the packet spends on the wire is decreased by 10 times, the minimum packet size also needs to be increased by 10x to ensure that it is long enough to reliably detect collisions. The speed of propagation in the wire is unaffected.

 

Problem 7-5C

A CSMA/CD network operates at 10Mb/s. The maximum distance between any pair of end hosts is 2km. What is the minimum size packet a host should send in order to detect collisions before it finishes transmitting a packet? Assume a propagation speed of 2 x 10^8m/s.

The answer:

• 200 bits

Explanation

Answer: P >= 2LR/c = 2 * 2000 * 10^7 / 2e8 = 200 bits

 

Problem 7-5D

Which of the following statements are true about a correctly sized CSMA/CD network?

The answers are:

• All collisions will be seen by every end host within the collision domain (not just the colliding hosts).
• If an end host has a new packet to send, it can send its packet immediately after determining if the network is idle.
• If the network uses Manchester encoding and there are three transitions every bit time we can safely conclude there is a collision.

Explanation

A is true because simultaneously transmitted packets are guaranteed to “overlap” at every point in the network (although the overlap will be different in different places).

C is true by design of CSMA/CD.

D is not true because a correct sequence of all 0’s or all 1’s will have two transitions per bit time.

E is true because a single packet cannot generate more than two transitions per bit time.