Protocol Data Units at each layer in Computer Networks - Time & Space Complexity

Time Complexity: Protocol Data Units at each layer

O(1)

Understanding Time Complexity

When data travels through a network, it passes through several layers. Each layer adds or removes information in units called Protocol Data Units (PDUs).

We want to understand how the processing time grows as data moves through these layers.

Scenario Under Consideration

Analyze the time complexity of processing PDUs through network layers.

// Simplified PDU processing through layers
function processData(data) {
  let pdu = data;
  pdu = applicationLayer(pdu);  // Adds headers
  pdu = transportLayer(pdu);    // Adds headers
  pdu = networkLayer(pdu);      // Adds headers
  pdu = dataLinkLayer(pdu);     // Adds headers
  return pdu;
}
    

This code shows data being wrapped with headers at each network layer to form PDUs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sequential processing through each network layer.
• How many times: Exactly once per layer, with a fixed number of layers.

How Execution Grows With Input

The processing steps do not increase with the size of the data but depend on the fixed number of layers.

Input Size (n)	Approx. Operations
10 bytes	4 steps (one per layer)
100 bytes	4 steps (one per layer)
1000 bytes	4 steps (one per layer)

Pattern observation: The number of steps stays the same regardless of data size.

Final Time Complexity

Time Complexity: O(1)

This means processing time stays constant because the number of layers is fixed and does not grow with data size.

Common Mistake

[X] Wrong: "Processing time grows with the size of the data because each layer adds headers."

[OK] Correct: Each layer processes the data once regardless of size; the number of layers is fixed, so time does not increase with data size.

Interview Connect

Understanding fixed steps in layered processing helps you explain how network protocols handle data efficiently. This skill shows you can reason about system design and performance.

Self-Check

"What if the number of network layers increased dynamically with data size? How would the time complexity change?"

Practice

1. Which Protocol Data Unit (PDU) name is used at the Network layer in the OSI model?

easy

A. Segment

B. Frame

C. Packet

D. Bit

Solution

1. Step 1: Recall OSI model layers and their PDUs

   The OSI model has seven layers. Each layer uses a specific PDU name. The Network layer is the third layer.

2. Step 2: Identify the PDU for the Network layer

   The Network layer uses the term 'Packet' for its PDU, which contains logical addressing information.

3. Final Answer:

   Packet -> Option C

4. Quick Check:

   Network layer PDU = Packet [OK]

Hint: Network layer always uses 'Packet' as its PDU name [OK]

Common Mistakes:

• Confusing Frame (Data Link layer) with Packet
• Mixing Segment (Transport layer) with Packet
• Thinking Bit is a PDU name at any layer

2. Which of the following correctly matches the PDU name with the Transport layer?

easy

A. Frame

B. Bit

C. Packet

D. Segment

Solution

1. Step 1: Identify the Transport layer in the OSI model

   The Transport layer is the fourth layer and is responsible for end-to-end communication.

2. Step 2: Recall the PDU name for the Transport layer

   The Transport layer uses 'Segment' as its PDU name, which contains data with transport headers.

3. Final Answer:

   Segment -> Option D

4. Quick Check:

   Transport layer PDU = Segment [OK]

Hint: Transport layer PDU is always called Segment [OK]

Common Mistakes:

• Choosing Frame which belongs to Data Link layer
• Selecting Packet which belongs to Network layer
• Confusing Bit with a PDU name

3. Consider this simplified data flow: Application data is passed down to the Transport layer, then to the Network layer, and finally to the Data Link layer. What is the correct sequence of PDUs at each layer?

medium

A. Packet -> Segment -> Frame

B. Segment -> Packet -> Frame

C. Frame -> Packet -> Segment

D. Bit -> Segment -> Packet

Solution

1. Step 1: Identify PDUs for each layer in order

   Transport layer uses Segment, Network layer uses Packet, Data Link layer uses Frame.

2. Step 2: Arrange PDUs in the order data passes down

   Data flows from Transport (Segment) -> Network (Packet) -> Data Link (Frame).

3. Final Answer:

   Segment -> Packet -> Frame -> Option B

4. Quick Check:

   Transport=Segment, Network=Packet, Data Link=Frame [OK]

Hint: Remember data flows: Segment, Packet, then Frame [OK]

Common Mistakes:

• Mixing order of PDUs
• Confusing Packet and Segment
• Including Bit as a PDU in this sequence

4. A student wrote this statement: "The Data Link layer PDU is called a Packet." What is wrong with this statement?

medium

A. Packet is the PDU for the Network layer, not Data Link layer.

B. Packet is the PDU for the Transport layer, not Data Link layer.

C. Packet is the PDU for the Application layer, not Data Link layer.

D. Packet is the PDU for the Physical layer, not Data Link layer.

Solution

1. Step 1: Identify the correct PDU for Data Link layer

   The Data Link layer uses 'Frame' as its PDU, not 'Packet'.

2. Step 2: Identify which layer uses 'Packet'

   The Network layer uses 'Packet' as its PDU.

3. Final Answer:

   Packet is the PDU for the Network layer, not Data Link layer. -> Option A

4. Quick Check:

   Data Link = Frame, Network = Packet [OK]

Hint: Data Link layer PDU is Frame, not Packet [OK]

Common Mistakes:

• Confusing Packet with Frame
• Mixing up Network and Data Link layers
• Assuming Packet is a general PDU name

5. In a network communication, data is encapsulated at each layer with its PDU. If a message is 1000 bytes at the Application layer, and each layer adds a header of 20 bytes (Transport), 30 bytes (Network), and 14 bytes (Data Link), what is the total size of the Frame sent over the Physical layer?

hard

A. 1064 bytes

B. 1066 bytes

C. 1064 bits

D. 1064 kilobytes

Solution

1. Step 1: Calculate total header size added by layers

   Transport header = 20 bytes, Network header = 30 bytes, Data Link header = 14 bytes. Total headers = 20 + 30 + 14 = 64 bytes.

2. Step 2: Add headers to original Application data size

   Application data = 1000 bytes. Total Frame size = 1000 + 64 = 1064 bytes.

3. Final Answer:

   1064 bytes -> Option A

4. Quick Check:

   1000 + 20 + 30 + 14 = 1064 bytes [OK]

Hint: Add all headers in bytes to original data size [OK]

Common Mistakes:

• Confusing bytes with bits
• Adding headers incorrectly
• Misreading units as kilobytes