Host-based routing in Kubernetes - Time & Space Complexity

Time Complexity: Host-based routing

O(n)

Understanding Time Complexity

We want to understand how the time to route requests grows as we add more hosts in Kubernetes.

How does the system handle more hosts and how does that affect routing speed?

Scenario Under Consideration

Analyze the time complexity of the following Kubernetes Ingress configuration snippet.

apiVersion: networking.k8s.io/v1
kind: Ingress
metadata:
  name: example-ingress
spec:
  rules:
  - host: host1.example.com
    http:
      paths:
      - path: /
        pathType: Prefix
        backend:
          service:
            name: service1
            port:
              number: 80
  - host: host2.example.com
    http:
      paths:
      - path: /
        pathType: Prefix
        backend:
          service:
            name: service2
            port:
              number: 80

This snippet routes requests to different services based on the host name in the request.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the host name against each rule in the Ingress rules list.
• How many times: Once per incoming request, the system compares the request host to each host rule until it finds a match.

How Execution Grows With Input

As the number of host rules increases, the system checks more hosts to find the right one.

Input Size (n)	Approx. Operations
10 hosts	Up to 10 host checks per request
100 hosts	Up to 100 host checks per request
1000 hosts	Up to 1000 host checks per request

Pattern observation: The number of checks grows linearly with the number of hosts.

Final Time Complexity

Time Complexity: O(n)

This means the routing time grows directly in proportion to the number of host rules.

Common Mistake

[X] Wrong: "Routing time stays the same no matter how many hosts are added."

[OK] Correct: Each new host adds another check, so more hosts mean more work to find the right route.

Interview Connect

Understanding how routing scales helps you design systems that stay fast as they grow. This skill shows you can think about real-world system behavior.

Self-Check

What if the routing used a hash map to find hosts instead of checking each one? How would the time complexity change?

Practice

1. What is the main purpose of host-based routing in Kubernetes Ingress?

easy

A. To encrypt all incoming traffic automatically.

B. To balance traffic evenly across all nodes in the cluster.

C. To monitor the health of backend services.

D. To send traffic to different services based on the website address (host).

Solution

1. Step 1: Understand host-based routing concept

   Host-based routing directs requests to services depending on the host name in the URL.

2. Step 2: Compare options to the concept

   Only To send traffic to different services based on the website address (host). matches this behavior; others describe different features.

3. Final Answer:

   To send traffic to different services based on the website address (host). -> Option D

4. Quick Check:

   Host-based routing = directing traffic by host [OK]

Hint: Host-based routing uses website address to choose service [OK]

Common Mistakes:

• Confusing host-based routing with load balancing
• Thinking it encrypts traffic automatically
• Assuming it monitors service health

2. Which of the following is the correct way to specify host-based routing in a Kubernetes Ingress YAML?

easy

A. spec:
host: example.com
paths:
- path: /
serviceName: my-service
servicePort: 80

B. spec:
rules:
- host: example.com
http:
paths:
- path: /
pathType: Prefix
backend:
service:
name: my-service
port:
number: 80

C. metadata:
host: example.com
spec:
service:
name: my-service
port: 80

D. spec:
rules:
- path: example.com
backend:
serviceName: my-service
servicePort: 80

Solution

1. Step 1: Review Kubernetes Ingress host-based routing syntax

   The correct syntax uses 'rules' with 'host' and 'http.paths' specifying backend service details.

2. Step 2: Match options to correct syntax

   spec: rules: - host: example.com http: paths: - path: / pathType: Prefix backend: service: name: my-service port: number: 80 matches the official Kubernetes Ingress spec format for host-based routing.

3. Final Answer:

   spec: rules: - host: example.com http: paths: - path: / pathType: Prefix backend: service: name: my-service port: number: 80 -> Option B

4. Quick Check:

   Correct Ingress host syntax = spec: rules: - host: example.com http: paths: - path: / pathType: Prefix backend: service: name: my-service port: number: 80 [OK]

Hint: Look for 'rules' with 'host' and 'http.paths' in Ingress YAML [OK]

Common Mistakes:

• Placing 'host' under metadata instead of rules
• Using deprecated 'serviceName' and 'servicePort' keys
• Confusing 'path' with 'host' field

3. Given this Ingress rule snippet, what service will receive traffic for host 'app.example.com'?

spec:
  rules:
  - host: app.example.com
    http:
      paths:
      - path: /app
        pathType: Prefix
        backend:
          service:
            name: app-service
            port:
              number: 8080
      - path: /
        pathType: Prefix
        backend:
          service:
            name: default-service
            port:
              number: 80

medium

A. Traffic to app.example.com with path starting /app goes to app-service; others go to default-service.

B. Traffic to app.example.com is rejected because of duplicate host rules.

C. Traffic to app.example.com goes only to default-service on port 80.

D. All traffic to app.example.com goes to app-service on port 8080.

Solution

1. Step 1: Analyze the Ingress rules for host 'app.example.com'

   The rule for host 'app.example.com' has two paths: '/app' and '/'.

2. Step 2: Understand path matching priority

   Requests with path starting '/app' go to 'app-service' on port 8080; all other paths go to 'default-service' on port 80.

3. Final Answer:

   Traffic to app.example.com with path starting /app goes to app-service; others go to default-service. -> Option A

4. Quick Check:

   Host + path routing = Traffic to app.example.com with path starting /app goes to app-service; others go to default-service. [OK]

Hint: Check host and path rules separately to find matching service [OK]

Common Mistakes:

• Assuming all traffic goes to first service listed
• Thinking duplicate hosts cause rejection
• Ignoring path prefixes in routing

4. You created this Ingress YAML but traffic to 'shop.example.com' is not routed correctly. What is the error?

spec:
  rules:
  - host: shop.example.com
    http:
      paths:
      - path: /shop
        backend:
          serviceName: shop-service
          servicePort: 80

medium

A. The keys 'serviceName' and 'servicePort' are deprecated; use 'service.name' and 'service.port.number'.

B. The host field is missing under metadata.

C. The path should be '/' instead of '/shop'.

D. The Ingress resource must have a selector field.

Solution

1. Step 1: Check Ingress backend service syntax

   Modern Kubernetes Ingress requires 'service.name' and 'service.port.number' keys, not 'serviceName' and 'servicePort'.

2. Step 2: Identify the error in YAML

   The YAML uses deprecated keys causing routing failure.

3. Final Answer:

   The keys 'serviceName' and 'servicePort' are deprecated; use 'service.name' and 'service.port.number'. -> Option A

4. Quick Check:

   Use correct backend service keys = The keys 'serviceName' and 'servicePort' are deprecated; use 'service.name' and 'service.port.number'. [OK]

Hint: Use 'service.name' and 'service.port.number' in Ingress backend [OK]

Common Mistakes:

• Using old 'serviceName' and 'servicePort' keys
• Adding host under metadata instead of rules
• Changing path unnecessarily

5. You want to run two websites, 'blog.example.com' and 'shop.example.com', on the same Kubernetes cluster using one Ingress. How should you configure the Ingress rules for host-based routing?

hard

A. Create one rule with host 'example.com' and use paths '/blog' and '/shop' to route to services.

B. Create separate Ingress resources for each host with identical paths.

C. Create two rules under spec.rules, each with a different host and paths pointing to their respective services.

D. Use a single rule with no host specified and rely on path prefixes only.

Solution

1. Step 1: Understand host-based routing for multiple hosts

   To route traffic by host, define separate rules for each host under spec.rules.

2. Step 2: Compare options for best practice

   Create two rules under spec.rules, each with a different host and paths pointing to their respective services. correctly uses two rules with different hosts and paths to route traffic properly.

3. Final Answer:

   Create two rules under spec.rules, each with a different host and paths pointing to their respective services. -> Option C

4. Quick Check:

   Multiple hosts need separate rules = Create two rules under spec.rules, each with a different host and paths pointing to their respective services. [OK]

Hint: Use separate rules for each host in one Ingress resource [OK]

Common Mistakes:

• Using one host with path prefixes instead of separate hosts
• Creating multiple Ingresses unnecessarily
• Not specifying hosts and relying on paths only