Ethernet protocol basics in Computer Networks - Time & Space Complexity

Time Complexity: Ethernet protocol basics

O(n)

Understanding Time Complexity

When working with Ethernet, it's important to understand how the time to send data grows as the amount of data increases.

We want to know how the protocol handles data transmission as network traffic grows.

Scenario Under Consideration

Analyze the time complexity of sending multiple Ethernet frames over a network.

for each frame in frames:
    wait until the line is free
    send frame
    wait for acknowledgment or timeout

This code sends each Ethernet frame one by one, waiting for the line to be free before sending.

Identify Repeating Operations

Look at what repeats as more frames are sent.

• Primary operation: Sending each frame after waiting for the line to be free.
• How many times: Once per frame, repeated for all frames in the list.

How Execution Grows With Input

As the number of frames increases, the total time to send all frames grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	10 waits and sends
100	100 waits and sends
1000	1000 waits and sends

Pattern observation: Doubling the number of frames roughly doubles the total time needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to send frames grows linearly with the number of frames.

Common Mistake

[X] Wrong: "Sending more frames doesn't affect total time much because Ethernet is fast."

[OK] Correct: Even though Ethernet is fast, each frame still takes time to send and wait for the line to be free, so more frames mean more total time.

Interview Connect

Understanding how Ethernet handles multiple frames helps you think about network speed and delays in real systems.

Self-Check

"What if multiple devices could send frames at the same time? How would that affect the time complexity?"

Practice

1. What is the primary purpose of the Ethernet protocol in computer networks?

easy

A. To define how devices communicate over a local area network

B. To assign IP addresses to devices

C. To encrypt data sent over the internet

D. To manage wireless connections

Solution

1. Step 1: Understand Ethernet's role

   Ethernet is a protocol used mainly for communication within local area networks (LANs).

2. Step 2: Compare with other network functions

   Assigning IP addresses is done by DHCP, encryption by security protocols, and wireless management by Wi-Fi standards.

3. Final Answer:

   To define how devices communicate over a local area network -> Option A

4. Quick Check:

   Ethernet = LAN communication [OK]

Hint: Ethernet is about local network communication [OK]

Common Mistakes:

• Confusing Ethernet with IP address assignment
• Thinking Ethernet manages wireless connections
• Assuming Ethernet encrypts data

2. Which part of an Ethernet frame contains the unique hardware address of the sending device?

easy

A. Payload

B. Destination IP address

C. Frame Check Sequence

D. Source MAC address

Solution

1. Step 1: Identify frame components

   An Ethernet frame includes source and destination MAC addresses, payload, and error-checking fields.

2. Step 2: Locate the sender's hardware address

   The source MAC address field holds the unique hardware address of the sending device.

3. Final Answer:

   Source MAC address -> Option D

4. Quick Check:

   Sender's hardware = Source MAC address [OK]

Hint: Source MAC = sender's hardware address [OK]

Common Mistakes:

• Confusing payload with address fields
• Mixing IP address with MAC address
• Thinking Frame Check Sequence holds addresses

3. Consider this simplified Ethernet frame structure:
Destination MAC | Source MAC | Type | Payload | CRC
Which part is responsible for detecting errors in the frame?

medium

A. Type

B. Payload

C. CRC

D. Source MAC

Solution

1. Step 1: Understand frame fields

   The CRC (Cyclic Redundancy Check) field is used to detect errors in the frame data.

2. Step 2: Differentiate other fields

   Type indicates the protocol, Payload carries data, and Source MAC is the sender's address, none detect errors.

3. Final Answer:

   CRC -> Option C

4. Quick Check:

   Error detection = CRC [OK]

Hint: CRC checks for errors in Ethernet frames [OK]

Common Mistakes:

• Confusing Type field with error detection
• Assuming Payload includes error checking
• Mixing Source MAC with error detection

4. A network technician notices that Ethernet frames are being dropped due to collisions. Which Ethernet feature helps to reduce collisions in a shared network?

medium

A. MAC Address Filtering

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

C. IP Addressing

D. Encryption

Solution

1. Step 1: Identify collision handling method

   CSMA/CD is the Ethernet protocol feature that listens before sending and detects collisions to reduce frame loss.

2. Step 2: Eliminate unrelated options

   IP addressing manages network layer routing, MAC filtering controls access, and encryption secures data, none reduce collisions.

3. Final Answer:

   Carrier Sense Multiple Access with Collision Detection (CSMA/CD) -> Option B

4. Quick Check:

   Collision reduction = CSMA/CD [OK]

Hint: CSMA/CD manages collisions in Ethernet [OK]

Common Mistakes:

• Confusing IP addressing with collision control
• Thinking MAC filtering prevents collisions
• Assuming encryption affects collisions

5. You want to design a network where devices communicate using Ethernet frames but avoid collisions entirely. Which modern Ethernet technology should you choose?

hard

A. Full-duplex Ethernet with switches

B. Half-duplex Ethernet with hubs

C. Wireless Ethernet with CSMA/CA

D. Token Ring Ethernet

Solution

1. Step 1: Understand collision domains

   Half-duplex Ethernet with hubs shares the medium, causing collisions; full-duplex with switches separates devices.

2. Step 2: Evaluate options for collision avoidance

   Full-duplex Ethernet with switches allows simultaneous send/receive without collisions. Wireless uses CSMA/CA, not Ethernet. Token Ring is a different protocol.

3. Final Answer:

   Full-duplex Ethernet with switches -> Option A

4. Quick Check:

   No collisions = Full-duplex + switches [OK]

Hint: Switches + full-duplex avoid Ethernet collisions [OK]

Common Mistakes:

• Choosing hubs which cause collisions
• Confusing wireless CSMA/CA with Ethernet collision control
• Thinking Token Ring is Ethernet