Encapsulation and decapsulation in Computer Networks - Time & Space Complexity

Time Complexity: Encapsulation and decapsulation

O(n)

Understanding Time Complexity

When data moves through a network, it is wrapped and unwrapped in layers. We want to understand how the time to do this wrapping and unwrapping changes as the data or layers increase.

How does the work grow when more layers or bigger data packets are involved?

Scenario Under Consideration

Analyze the time complexity of the following process for encapsulation and decapsulation.

function encapsulate(data, layers) {
  for (let i = 0; i < layers; i++) {
    data = addHeaderAndFooter(data, i);
  }
  return data;
}

function decapsulate(data, layers) {
  for (let i = 0; i < layers; i++) {
    data = removeHeaderAndFooter(data);
  }
  return data;
}
    

This code adds or removes headers and footers layer by layer to data as it moves through the network.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: Adding or removing headers and footers for each layer.
• How many times: Once for each layer, repeated in a simple loop.

How Execution Grows With Input

As the number of layers increases, the work to add or remove headers grows in a straight line.

Input Size (layers)	Approx. Operations
10	10 header/footer additions or removals
100	100 header/footer additions or removals
1000	1000 header/footer additions or removals

Pattern observation: The work grows evenly as layers increase, doubling layers doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to encapsulate or decapsulate grows directly with the number of layers.

Common Mistake

[X] Wrong: "Adding more layers does not affect time much because each layer is small."

[OK] Correct: Even small layers add work, and more layers mean more repeated steps, so time grows steadily with layers.

Interview Connect

Understanding how work grows with layers helps you explain network processing clearly and shows you can think about efficiency in real systems.

Self-Check

"What if the data size also grows with each layer? How would the time complexity change?"

Practice

1. What is the main purpose of encapsulation in computer networks?

easy

A. To encrypt data for security

B. To add headers to data before sending it

C. To remove headers from data after receiving it

D. To compress data to save space

Solution

1. Step 1: Understand encapsulation role

   Encapsulation means adding headers to data to prepare it for sending over a network.

2. Step 2: Differentiate from decapsulation

   Decapsulation is the opposite, removing headers after receiving data.

3. Final Answer:

   To add headers to data before sending it -> Option B

4. Quick Check:

   Encapsulation = Adding headers [OK]

Hint: Encapsulation adds headers; decapsulation removes them [OK]

Common Mistakes:

• Confusing encapsulation with decapsulation
• Thinking encapsulation encrypts data
• Assuming encapsulation compresses data

2. Which of the following correctly describes the order of operations in encapsulation?

easy

A. Data -> Add header -> Send

B. Send -> Add header -> Data

C. Add header -> Data -> Send

D. Data -> Send -> Add header

Solution

1. Step 1: Identify encapsulation steps

   Encapsulation starts with data, then adds a header, then sends the packet.

2. Step 2: Check option order

   Data -> Add header -> Send shows the correct sequence: Data -> Add header -> Send.

3. Final Answer:

   Data -> Add header -> Send -> Option A

4. Quick Check:

   Encapsulation order = Data, header, send [OK]

Hint: Headers are added after data, before sending [OK]

Common Mistakes:

• Mixing up the order of adding headers and sending
• Thinking headers are added after sending
• Confusing data and header order

3. Consider a network packet that has been encapsulated with three headers: Application, Transport, and Network layers. When the packet reaches the destination, which header is removed first during decapsulation?

medium

A. Network layer header

B. Data payload

C. Application layer header

D. Transport layer header

Solution

1. Step 1: Understand decapsulation order

   Decapsulation removes headers in reverse order of encapsulation, starting from the outermost header.

2. Step 2: Identify outermost header

   The Network layer header is the outermost, then the extra header (if any), then the Transport layer header, and finally the Application layer header is innermost.

3. Step 3: Correct header removal order

   Since the Application layer header is innermost, the first header removed is the Transport layer header, which is just outside the Application layer header.

4. Final Answer:

   Transport layer header -> Option D

5. Quick Check:

   Decapsulation removes headers from outermost to innermost, so Transport header is removed before Application header [OK]

Hint: Remove headers from outermost to innermost [OK]

Common Mistakes:

• Removing inner headers before outer ones
• Confusing application header as outermost
• Thinking data payload is a header

4. A network device is supposed to decapsulate a packet but fails to remove the transport layer header. What problem is most likely to occur?

medium

A. The packet will be sent back to the sender automatically

B. The data will be delivered correctly without issues

C. The receiving application may not understand the data

D. The network layer header will be removed twice

Solution

1. Step 1: Understand decapsulation importance

   Removing headers properly is needed so the receiving application gets clean data.

2. Step 2: Consequence of not removing transport header

   If the transport header remains, the application layer may receive unexpected data and fail to understand it.

3. Final Answer:

   The receiving application may not understand the data -> Option C

4. Quick Check:

   Incomplete decapsulation causes application errors [OK]

Hint: All headers must be removed for correct data delivery [OK]

Common Mistakes:

• Assuming data is always delivered correctly
• Thinking network layer header removal affects this
• Believing packets auto-return on errors

5. You are designing a custom protocol that requires adding an extra header between the transport and network layers during encapsulation. How should decapsulation be adjusted to correctly process this packet?

hard

A. Remove the extra header after the network layer header during decapsulation

B. Remove the extra header before the network layer header during decapsulation

C. Ignore the extra header during decapsulation

D. Remove the extra header after the transport layer header during decapsulation

Solution

1. Step 1: Identify header order in encapsulation

   The extra header is added between transport and network layers, so it is inside the network header but outside the transport header.

2. Step 2: Determine decapsulation order

   Decapsulation removes headers from outermost to innermost, so after removing the network header, the extra header should be removed next.

3. Final Answer:

   Remove the extra header after the network layer header during decapsulation -> Option A

4. Quick Check:

   Decapsulation order matches encapsulation reverse [OK]

Hint: Remove headers in reverse order of adding [OK]

Common Mistakes:

• Removing extra header before network header
• Ignoring the extra header completely
• Removing extra header after transport header