Path-based routing in Kubernetes - Time & Space Complexity

Time Complexity: Path-based routing

O(n)

Understanding Time Complexity

We want to understand how the time to route requests changes as the number of paths grows in Kubernetes.

How does the system decide which backend to send a request to when many paths exist?

Scenario Under Consideration

Analyze the time complexity of the following Kubernetes Ingress path-based routing rules.

apiVersion: networking.k8s.io/v1
kind: Ingress
metadata:
  name: example-ingress
spec:
  rules:
  - http:
      paths:
      - path: /app1
        pathType: Prefix
        backend:
          service:
            name: app1-service
            port:
              number: 80
      - path: /app2
        pathType: Prefix
        backend:
          service:
            name: app2-service
            port:
              number: 80
      # ... more paths ...

This snippet routes incoming requests to different services based on the URL path prefix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each path rule in order to find a match for the request path.
• How many times: The system may check up to all path rules (n) in the worst case.

How Execution Grows With Input

As the number of path rules increases, the system checks more paths one by one until it finds a match.

Input Size (n)	Approx. Operations
10	Up to 10 path checks
100	Up to 100 path checks
1000	Up to 1000 path checks

Pattern observation: The number of checks grows directly with the number of paths.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the right path grows linearly as you add more paths.

Common Mistake

[X] Wrong: "The routing time stays the same no matter how many paths exist."

[OK] Correct: Each new path adds a possible check, so more paths mean more work to find the match.

Interview Connect

Understanding how routing scales helps you design efficient systems and explain trade-offs clearly in real projects.

Self-Check

"What if the paths were stored in a tree structure instead of a list? How would the time complexity change?"

Practice

1. What does path-based routing in Kubernetes Ingress do?

easy

A. It sends traffic to different services based on URL paths.

B. It balances traffic evenly between all nodes.

C. It encrypts traffic between pods.

D. It schedules pods on specific nodes.

Solution

1. Step 1: Understand Ingress role

   Kubernetes Ingress manages external access to services, often HTTP.

2. Step 2: Identify path-based routing function

   Path-based routing directs requests to services depending on the URL path.

3. Final Answer:

   It sends traffic to different services based on URL paths. -> Option A

4. Quick Check:

   Path-based routing = directing traffic by URL path [OK]

Hint: Remember: path-based routing matches URL paths to services [OK]

Common Mistakes:

• Confusing path-based routing with load balancing
• Thinking it schedules pods
• Assuming it encrypts traffic

2. Which is the correct way to specify a path in a Kubernetes Ingress rule for path-based routing?

easy

A. url: /app
urlType: Prefix

B. route: /app
routeType: Exact

C. servicePath: /app
serviceType: Exact

D. path: /app
pathType: Prefix

Solution

1. Step 1: Recall Ingress rule syntax

   Ingress rules use path and pathType keys to define routing.

2. Step 2: Match correct keys and values

   Correct keys are path and pathType, with values like '/app' and 'Prefix'.

3. Final Answer:

   path: /app pathType: Prefix -> Option D

4. Quick Check:

   Use path and pathType keys for routing [OK]

Hint: Look for 'path' and 'pathType' keys in Ingress rules [OK]

Common Mistakes:

• Using wrong keys like 'route' or 'url'
• Mixing up pathType values
• Missing pathType field

3. Given this Ingress snippet, which service will receive traffic for URL path '/shop/cart'?

rules:
- http:
    paths:
    - path: /shop
      pathType: Prefix
      backend:
        service:
          name: shop-service
          port:
            number: 80
    - path: /blog
      pathType: Prefix
      backend:
        service:
          name: blog-service
          port:
            number: 80

medium

A. blog-service

B. shop-service

C. default backend

D. No service matches

Solution

1. Step 1: Check path matching rules

   Path '/shop/cart' starts with '/shop', matching the first path rule with pathType Prefix.

2. Step 2: Identify backend service

   The matching path routes to 'shop-service' on port 80.

3. Final Answer:

   shop-service -> Option B

4. Quick Check:

   Prefix match '/shop' routes to shop-service [OK]

Hint: Prefix path matches any URL starting with it [OK]

Common Mistakes:

• Choosing blog-service for /shop/cart
• Assuming no match for subpaths
• Confusing default backend with path rules

4. You wrote this Ingress rule but traffic to '/api' is not routed correctly:

paths:
- path: api
  pathType: Prefix
  backend:
    service:
      name: api-service
      port:
        number: 80

What is the likely error?

medium

A. Incorrect pathType value

B. Service name is invalid

C. Missing leading slash in path value

D. Port number must be a string

Solution

1. Step 1: Check path syntax

   Paths must start with a leading slash '/' to match URLs correctly.

2. Step 2: Identify missing slash

   The path is 'api' instead of '/api', so it won't match requests starting with '/api'.

3. Final Answer:

   Missing leading slash in path value -> Option C

4. Quick Check:

   Paths need leading '/' for correct matching [OK]

Hint: Always start path with '/' in Ingress rules [OK]

Common Mistakes:

• Omitting leading slash in path
• Using wrong pathType values
• Assuming port number must be string

5. You want to route traffic so that: - '/app' goes to 'app-service' - '/app/admin' goes to 'admin-service' Which Ingress path rules correctly implement this path-based routing?

hard

A. - path: /app/admin
pathType: Prefix
backend:
service:
name: admin-service
port:
number: 80
- path: /app
pathType: Prefix
backend:
service:
name: app-service
port:
number: 80

B. - path: /app
pathType: Prefix
backend:
service:
name: app-service
port:
number: 80
- path: /app/admin
pathType: Prefix
backend:
service:
name: admin-service
port:
number: 80

C. - path: /app
pathType: Exact
backend:
service:
name: app-service
port:
number: 80
- path: /app/admin
pathType: Exact
backend:
service:
name: admin-service
port:
number: 80

D. - path: /app/admin
pathType: Exact
backend:
service:
name: admin-service
port:
number: 80
- path: /app
pathType: Exact
backend:
service:
name: app-service
port:
number: 80

Solution

1. Step 1: Understand path matching order

   Ingress matches paths in order; more specific paths must come first to avoid being shadowed.

2. Step 2: Check rule order and pathType

   Placing '/app/admin' before '/app' with pathType Prefix ensures '/app/admin' routes to admin-service, others to app-service.

3. Final Answer:

   Place '/app/admin' rule before '/app' rule with Prefix pathType -> Option A

4. Quick Check:

   Order specific paths first for correct routing [OK]

Hint: List longer paths before shorter ones in Ingress rules [OK]

Common Mistakes:

• Placing general path before specific path
• Using Exact pathType causing no subpath matches
• Ignoring rule order importance