1

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Murphy McCauley

Discussion, Ethernet 🔗

Connecting Local Hosts

Ethernet

• Connecting Local Hosts
• Multiple Access Protocols
• Sending Packets
• Layer 2 Networks

Connecting Local Hosts

So far, we've assumed that every link connects exactly two machines:

R1

A

B

In reality, a single wire can connect multiple computers:

R1

A

B

A

B

C

Connecting Local Hosts

How could we connect hosts in a local network?

A

B

D

E

C

A

B

C

D

E

Mesh: Link between every pair of machines.

• For every new host, we have to add new links to every other host.
• Need a lot of (physical) ports per host.

Bus: A single wire for all machines.

• Introduces a shared media.

Shared Media

Shared media: Many machines using the same wire.

• If multiple machines transmit at the same time, signals will interfere or collide.
• Analogy: People talking simultaneously on a group call.

​

Note: Shared media is not necessarily a wire.

• Could be light signals on a shared optical fiber.
• Or radio waves on a shared wireless link.

A

B

C

D

E

Blah blah

Blah blah

??!

??!

??!

Multiple Access Protocols

Ethernet

• Connecting Local Hosts
• Multiple Access Protocols
• Sending Packets
• Layer 2 Networks

Multiple Access Protocols

A multiple access protocol allocates the shared media to everyone wanting to use it.

• 3 types of approaches.
• Several protocols of each type.

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (1/3) – Multiplexing

Idea: Allocate a fixed slice of resources to each node.

• Frequency-based multiplexing: Divide medium into frequency channels.
• Time-based multiplexing: Give each node some fixed time slots.

Problem: Can be wasteful.

​

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (2/3) – Taking Turns

Idea: Nodes take turns speaking.

• Polling protocols: A coordinator decides when each node can speak.
• Example: Bluetooth.
• Token passing: Pass a virtual token around. Only the node with the token can speak.

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (3/3) – Random Access

Idea: Nodes talk whenever they have something to say.

• Deal with collisions when they occur.
• Benefit: Simplicity. No coordinators or tokens.

​

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (3/3) – Random Access – ALOHA (Additive Links On-line Hawaii Area)

ALOHA random access scheme: "rude" version.

• If you have a packet, just send it.
• Recipient replies with an ack.
• If two nodes send simultaneously, collision corrupts the packets.
• No ack!
• If you don't get an ack: Wait some random amount of time, then resend.
• Randomness helps avoid another collision.

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (3/3) – Random Access – CSMA

CSMA (Carrier Sense Multiple Access): "polite" version.

• First, listen to see if anyone is sending.
• Only start sending when it's quiet.

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Multiple Access Protocols (3/3) – Random Access – CSMA and Propagation Delay

CSMA does not necessarily avoid collisions, because of propagation delay.

• t=0: B starts sending.
• Signal takes time to reach A, C, D.
• t=2: D wants to send.
• Signal hasn't reached D yet!
• D thinks it's quiet and starts sending.
• Result: Collision!

A

B

C

D

time

space

Multiple Access Protocols (3/3) – Random Access – CSMA/CD

CSMA/CD (Carrier Sense Multiple Access with Collision Detection):

• Listen before sending, but also while you're sending.
• If you hear someone else sending, stop! Collision detected.

CSMA/CD uses binary exponential backoff:

• After every collision, wait up to twice as long before resending.
• After first collision: Wait between 0–4 seconds.
• If resend collides again: Wait between 0–8 seconds.
• Resends fast when possible, slowing down when necessary (e.g. many senders).

CSMA/CD

CSMA

ALOHA

Tokens

Polling

Multiplexing

Taking Turns

Random Access

Multiple Access Protocols

Frequency

Time

Sending Ethernet Packets

Ethernet

• Connecting Local Hosts
• Multiple Access Protocols
• Sending Packets
• Layer 2 Networks

​

Ethernet as LAN Network Protocol

Local Area Networks (LANs) are generally Ethernet.

Machines in the same LAN can exchange messages directly at Layer 2!

• No need for IPs, routers, forwarding, etc.
• Analogy: If we're in the same room, we can talk without using the postal system.

Ethernet Addressing

At layer 2, each machine has a MAC address (Media Access Control).

• Can be used even if you don't have an IP address.
• 48 bits, written in hex, e.g. f8:ff:c2:2b:36:16.
• Stored permanently on the machine ("burned in").
• Often can be overridden by software.
• Allocated according to organization, e.g. manufacturer of the machine.
• Globally unique. You might plug your computer in anywhere.

00

0111111111111101000011

110101000110110001101000

2 bits of flags

22-bit manufacturer ID

24-bit�machine ID

Beware of endianness.

Types of LAN Communication

Ethernet supports three types of communication:

• Unicast: Send a packet to a single recipient.
• Broadcast: Send a packet to everyone on the local network.
• Multicast: Send a packet to everyone in a specific group.
• Machines in the local network can join groups.

Types of LAN Communication (1/3) – Unicast

Unicast: Send a packet to a single recipient.

• Destination = the recipient's MAC address.

​

Recall: On a shared medium, everybody gets the signal.

• When you get a packet, check the destination to see if it's meant for you.
• If not, ignore the packet.

Types of LAN Communication (2/3) – Broadcast

Broadcast: Send a packet to everyone on the local network.

• Packet already reaches everybody on the shared medium.
• We just need to make sure everyone knows it's meant for them.
• Destination = the broadcast address, FF:FF:FF:FF:FF:FF.

Types of LAN Communication (3/3) – Multicast

Multicast: Send a packet to everyone in a specific group.

• Again, everyone gets the packet – need to ensure the group knows it's for them.
• Each group has a group address.
• Individual computer's address: First bit 0.
• Group address: First bit 1.
• Broadcast is just a special case of multicast, where everyone is in a group.

10

0111111111111101000011

110101000110110001101000

If this bit is 1, it's a group address.

Beware of endianness.

Ethernet Packet Structure

A data packet in Ethernet is often called a frame.

• Many fields (destination, source, type, checksum) similar to IP header.
• Need additional fields to separate packets on the wire.

Preamble (7)

SFD (1)

Destination MAC (6)

Source�MAC (6)

Type (2)

Payload

FCS (4)

IPG (12)

Signal start of new packet on wire

Destination

Demultiplex�(is payload IPv4 or IPv6?)

Source

Signal end of packet on wire

Checksum

Layer 2 Networks

Ethernet

• Connecting Local Hosts
• Multiple Access Protocols
• Sending Packets
• Layer 2 Networks

​

Layer 2 Networks

We could use more than one wire in a local network.

Switches need to forward packets toward their destination.

• If a switch receives a broadcast packet: Send it to every neighbor.
• Multicast is more complicated. Need to know who's in the group.

S2

S1

A

S3

S3

B

C

D

Layer 2 Networks

Routing protocols from Layer 3 can also be used at Layer 2.

• Destinations are MAC addresses, instead of IP addresses.

Problem: MAC addresses can't be aggregated.

• Allocated by manufacturer, not geographically.
• This is why Layer 2 can't scale to the Internet.

S2

S1

A

S3

S3

B

C

D