Content Delivery Networks (CDN) in Computer Networks - Time & Space Complexity

Time Complexity: Content Delivery Networks (CDN)

O(n)

Understanding Time Complexity

When studying CDNs, it is important to understand how the time to serve content changes based on the number of users, edge servers, and cached items.

We want to know how cache lookup and content retrieval scale as CDN infrastructure grows.

Scenario Under Consideration

Analyze the time complexity of the following simplified CDN cache lookup process.

for each incoming_request in requests:
    cache_key = hash(request.url)
    if cache_key in edge_cache:
        return edge_cache[cache_key]
    else:
        content = fetch_from_origin(request.url)
        edge_cache[cache_key] = content
        return content

This code processes each user request by computing a hash of the URL, checking the edge cache, and either returning cached content or fetching from the origin.

Identify Repeating Operations

Look at the operations performed for each request.

• Primary operation: Hash computation and cache lookup for each request.
• How many times: Once per incoming request. The cache lookup itself is a hash table operation.

How Execution Grows With Input

As the number of requests grows, the total work increases linearly, but each individual lookup remains constant time.

Input Size (n requests)	Cache Lookups	Origin Fetches (worst case)
100 requests	100 (O(1) each)	100 (all unique URLs)
1,000 requests	1,000 (O(1) each)	~200 (most are cache hits)
10,000 requests	10,000 (O(1) each)	~500 (high cache hit rate)

Pattern observation: Cache lookups scale linearly with requests, but origin fetches grow much slower because repeated URLs are served from cache. The cache hit ratio improves as more content gets cached.

Final Time Complexity

Time Complexity: O(n) for processing n requests

Each request requires O(1) for the hash computation and cache lookup. Processing n total requests takes O(n) time. The key insight is that origin fetches (the expensive operation) decrease as the cache warms up.

Common Mistake

[X] Wrong: "Every request requires fetching from the origin server, so the time grows with both requests and content size."

[OK] Correct: The entire purpose of a CDN cache is to avoid origin fetches. After the first request for a URL caches the content, all subsequent requests for the same URL are O(1) cache hits. The origin fetch only happens once per unique URL.

Interview Connect

Understanding CDN cache lookup complexity helps explain why CDNs can handle millions of requests per second. Each edge server performs O(1) lookups, and the distributed nature means total capacity scales linearly with the number of edge servers.

Self-Check

What if the cache has a fixed size and uses LRU eviction? How would the cache hit rate change for a CDN serving a long-tail distribution of URLs where a few URLs get most traffic?

Practice

1. What is the primary purpose of a Content Delivery Network (CDN)?

easy

A. To create new content for websites

B. To store copies of content on multiple servers worldwide to speed up delivery

C. To replace the main server completely

D. To encrypt all website data end-to-end

Solution

1. Step 1: Understand CDN's role in content delivery

   A CDN stores copies of website content on servers around the world to reduce the distance data travels.

2. Step 2: Identify the main benefit of CDN

   This reduces load on the main server and speeds up content delivery to users globally.

3. Final Answer:

   To store copies of content on multiple servers worldwide to speed up delivery -> Option B

4. Quick Check:

   CDN purpose = content caching and faster delivery [OK]

Hint: CDNs cache content globally to speed up access [OK]

Common Mistakes:

• Thinking CDN creates new content
• Believing CDN replaces main server
• Confusing CDN with encryption service

2. Which of the following is a correct characteristic of a CDN's edge server?

easy

A. It stores original content only at the main data center

B. It processes all user authentication requests

C. It replaces the DNS server for domain resolution

D. It caches content closer to users to reduce latency

Solution

1. Step 1: Define edge server role in CDN

   Edge servers cache content near users to reduce the time it takes to load data.

2. Step 2: Eliminate incorrect options

   Edge servers do not store only original content, handle authentication, or replace DNS servers.

3. Final Answer:

   It caches content closer to users to reduce latency -> Option D

4. Quick Check:

   Edge server = caches content near users [OK]

Hint: Edge servers cache content near users for speed [OK]

Common Mistakes:

• Confusing edge servers with main data center
• Assuming edge servers handle authentication
• Thinking edge servers replace DNS

3. Consider a CDN setup where a user requests a video file. The CDN edge server does not have the file cached. What happens next?

medium

A. The edge server redirects the user to another edge server

B. The edge server returns an error to the user immediately

C. The edge server fetches the file from the origin server and caches it

D. The edge server compresses the request and sends it back

Solution

1. Step 1: Understand cache miss in CDN

   If the edge server does not have the requested content, it must get it from the origin server.

2. Step 2: Describe caching after fetch

   After fetching, the edge server caches the content to serve future requests faster.

3. Final Answer:

   The edge server fetches the file from the origin server and caches it -> Option C

4. Quick Check:

   Cache miss = fetch from origin + cache [OK]

Hint: Cache miss triggers fetch from origin and caching [OK]

Common Mistakes:

• Thinking edge server returns error on cache miss
• Assuming user is redirected to another edge server
• Believing edge server compresses request instead

4. A CDN is configured but users report slow loading times from certain regions. What is the most likely cause?

medium

A. The CDN has no edge servers near those regions

B. The origin server is down globally

C. Users have slow internet unrelated to CDN

D. The CDN is encrypting content too much

Solution

1. Step 1: Analyze CDN coverage impact

   If edge servers are missing near certain regions, content must travel farther, causing delays.

2. Step 2: Rule out other causes

   Origin server down affects all users, slow internet is user-side, and encryption does not cause major delays.

3. Final Answer:

   The CDN has no edge servers near those regions -> Option A

4. Quick Check:

   Missing edge servers = slow regional load [OK]

Hint: No local edge servers cause regional slowness [OK]

Common Mistakes:

• Blaming origin server when issue is regional
• Ignoring CDN edge server distribution
• Assuming encryption causes slow loading

5. You are designing a CDN for a global video streaming service. Which combination of strategies will best improve performance and scalability?

hard

A. Use many edge servers worldwide and implement cache invalidation policies

B. Use a single large origin server and no caching at edges

C. Only cache static images and stream videos directly from origin

D. Disable caching and rely on user devices to store content

Solution

1. Step 1: Identify key CDN strategies for video streaming

   Many edge servers reduce latency globally; cache invalidation keeps content fresh.

2. Step 2: Evaluate other options

   Single origin server causes bottlenecks; no caching wastes bandwidth; disabling caching hurts performance.

3. Final Answer:

   Use many edge servers worldwide and implement cache invalidation policies -> Option A

4. Quick Check:

   Global edges + cache control = best scalability [OK]

Hint: Global edges plus cache policies boost CDN performance [OK]

Common Mistakes:

• Relying on single origin server only
• Not caching large video files
• Disabling caching entirely