Load Balancing & Request Routing

Overview

Load Balancing distributes inference requests across multiple GPU/node clusters. Request Routing intelligently directs requests to appropriate models (by size, task, latency). Critical for production LLM serving at scale.

• Strategies: Round-robin, least-loaded, latency-aware, task-aware
• Challenges: Heterogeneous hardware, variable request sizes, SLA maintenance
• Tools: vLLM, Ray Serve, KServe, Kubernetes
• Goal: Maximize throughput while maintaining latency SLAs

---

The Serving Challenge

Load Distribution Problem

Request stream:
Request 1: "What is the capital of France?" (simple, needs 5 tokens)
Request 2: "Write a 1000-word essay on climate change" (complex, needs 1000 tokens)
Request 3: "Translate this paragraph to 5 languages" (medium, needs 200 tokens)

Naive distribution:
Server 1: Request 1 (5 tokens, 50ms)
Server 2: Request 2 (1000 tokens, 10s)
Server 3: Request 3 (200 tokens, 2s)

Problem:
 - Server 1: Idle after 50ms
 - Server 2: Busy for 10s (Request 1 already done!)
 - Server 3: Intermediate
 - Utilization: ~33% average

Solution:
 - Distribute based on request size, not round-robin!
 - Predict time, load-balance, maximize utilization

-

Load Balancing Strategies

1. Round-Robin (Simplest)

Algorithm:
Request 1 → Server 1
Request 2 → Server 2
Request 3 → Server 3
Request 4 → Server 1 (cycle back)
...

Pros:
Simple, no overhead
Works reasonably well for uniform requests

Cons:
Ignores request size variance
Ignores server load differences
Not optimal

2. Least-Connections

Algorithm:
 - Track active connections per server
 - Route new request to server with fewest connections

Example:
Server 1: 3 active requests
Server 2: 7 active requests
Server 3: 2 active requests
 - New request → Server 3 (fewest)

Pros:
Simple to implement
Handles request count variation
Better than round-robin

Cons:
Ignores request duration
Short request stays longer than needed
Not accounting for request complexity

3. Least-Loaded (Queue-Length)

Algorithm:
 - Track tokens waiting to process (queue depth)
 - Route to server with fewest tokens

Example:
Server 1: Queue depth = 5000 tokens
Server 2: Queue depth = 2000 tokens
Server 3: Queue depth = 8000 tokens
 - New request (100 tokens) → Server 2

Pros:
Accounts for work volume
More accurate than connection count
Better throughput

Cons:
Requires tracking queue depth
Still not optimal (doesn't predict latency)

4. Latency-Aware Routing

Algorithm:
 - Predict latency for request on each server
 - Route to server with shortest predicted latency

Example:
New request: 200 tokens
Model: LLaMA 7B
GPU: A100

Server 1 (A100, new): Predicted latency = 200 × 50ms = 10s
Server 2 (A100, loaded with 5000 tokens): = 5000×50 + 200×50 = 260s
Server 3 (V100, new): Predicted latency = 200 × 100ms = 20s
 - Route to Server 1 (lowest latency)

Code:
```python
def predict_latency(server, request):
 """Predict request latency on server"""

 # Get server state
 queue_depth = server.queue_depth # tokens waiting
 num_active = server.active_requests
 throughput = server.throughput # tokens/sec

 # Predict time in queue
 time_in_queue = queue_depth / throughput

 # Predict processing time
 processing_time = request.tokens / throughput

 # Total latency
 total_latency = time_in_queue + processing_time

 return total_latency

# Route to minimum latency
best_server = min(servers, key=lambda s: predict_latency(s, request))

Pros: Most optimal routing strategy Directly optimizes user experience Handles heterogeneous hardware

Cons: Requires accurate throughput estimation More complex implementation

-

## Hardware Heterogeneity

### Challenge: Different GPUs

Scenario: Cluster with mixed hardware

Server 1: H100 (1000 tokens/sec) Server 2: A100 (300 tokens/sec) Server 3: A100 (300 tokens/sec)

Same request on different servers: Request: 100 tokens Server 1: 100ms (fast!) Server 2: 330ms (3x slower) Server 3: 330ms

Naive routing:

• Even distribution → 1 to each server
• Users get 100ms + 330ms + 330ms (very unbalanced SLA)

Smart routing:

• Send more requests to H100
• Route large batches to A100s
• Maintain consistent SLA across users

### Solution: Server Profiles

```python
class ServerProfile:
 def __init__(self, server_id, gpu_type, memory_gb):
 self.id = server_id
 self.gpu = gpu_type
 self.memory = memory_gb

 # Throughput by model size
 self.throughput = {
 '7B': 500 if 'H100' in gpu_type else 150,
 '13B': 300 if 'H100' in gpu_type else 80,
 '70B': 50 if 'H100' in gpu_type else 15,
 }

 def predict_latency(self, model_size, num_tokens):
 tps = self.throughput.get(model_size, 100)
 return num_tokens / tps

# Routing logic
best_server = min(
 servers,
 key=lambda s: s.predict_latency(request.model_size, request.tokens)
)

---

Advanced: Request Batching + Load Balancing

Continuous Batching with Load Balancing

Continuous batching already handles variable request sizes well!

With batching:
Request 1 arrives: Batch [Req1]
Request 2 arrives: Batch [Req1, Req2] (Req1 still processing)
Request 1 done: Batch [Req2]
Request 3 arrives: Batch [Req2, Req3]
Request 4 arrives: Batch [Req2, Req3, Req4]

Load balancing + batching:
 - Route new request to server with smallest batch
 - Server processes batch together
 - Finish request efficiently
 - Good utilization

Combined strategy:
```python
class LoadBalancedServer:
 def __init__(self):
 self.batch_queue = []
 self.batch_size = 32

 def route_request(self, request):
 # Find server with smallest batch queue
 best_server = min(
 self.servers,
 key=lambda s: len(s.batch_queue)
)

 best_server.batch_queue.append(request)

 # Process batch if full
 if len(best_server.batch_queue) >= self.batch_size:
 best_server.process_batch()

# Result

-

## Advanced: Model Selection

### Routing to Different Model Sizes

Scenario: Multiple model versions available

Models:

• 7B model: Fast, decent quality, 100 tokens/sec
• 13B model: Medium, good quality, 50 tokens/sec
• 70B model: Slow, excellent quality, 10 tokens/sec

Requests vary: Request 1: "Is Paris in France?" → Simple, 7B OK Request 2: "Analyze the economic impact..." → Complex, needs 70B

Smart routing:

1. Classify request complexity
2. Route to appropriate model
3. Balance load within model tier

Implementation:

def classify_request_complexity(request):
 """Simple heuristic for request complexity"""
 # Count special tokens, questions, entities
 complexity = (
 request.text.count("?") * 10 + # Questions need better model
 len(request.text.split()) / 10 # Length slightly matters
)
 return "simple" if complexity < 50 else "complex"

def route_by_complexity(request):
 complexity = classify_request_complexity(request)

 if complexity == "simple":
 servers = small_model_servers # 7B
 else:
 servers = large_model_servers # 70B

 # Load balance within tier
 return min(servers, key=lambda s: len(s.batch_queue))

-

Scaling Considerations

Horizontal vs Vertical Scaling

Horizontal (more servers):
 - Add Server 4, 5, 6...
 - Distribute load across multiple machines
 - Easier to scale (add commodity hardware)
 - Challenges: Network overhead, state management

Vertical (bigger GPUs):
 - Replace A100 with H100
 - Single server faster
 - Limited by single machine capacity
 - Expensive

Recommendation:
 - Combination: Large GPUs (H100) + many servers
 - Each server handles multiple requests efficiently
 - Many servers handle many users

SLA Management

SLA Requirements:
 - P99 latency < 1 second
 - P95 latency < 500ms
 - Throughput > 1000 req/sec

Load balancing for SLA:
 - Predict latency per request
 - Reject requests that would violate SLA (circuit breaker)
 - Queue excess requests for later
 - Maintain consistent experience

Code:
```python
def accept_request(request):
 """Check if accepting request maintains SLA"""

 # Predict latency if we accept
 predicted_latency = predict_latency_if_accept(request)

 if predicted_latency < SLA_THRESHOLD:
 return True # Accept
 else:
 return False # Reject, inform user to retry

---

## Production Systems

### vLLM + Load Balancer

vLLM: Built-in continuous batching Kubernetes: Horizontal pod autoscaling Load Balancer: NGINX with Lua scripting

Stack:

• ┌─────────────────┐
• Request Stream │
• ┬────────┘ ↓
• ┌─────────────────┐
• Load Balancer │ (NGINX)
• Routes by latency
• ┬────────┘
• ┌────┼────┬────┐ ↓ ↓ ↓ ↓ vLLM vLLM vLLM vLLM Pod1 Pod2 Pod3 Pod4

Each pod:

• Continuous batching
• Processes multiple requests
• Reports load metrics

Load balancer:

• Tracks metrics
• Routes intelligently
• Auto-scales via Kubernetes

```

---

Key Takeaways

Latency-aware routing: Most effective strategy Account for hardware heterogeneity in predictions Combine with continuous batching for efficiency Model-aware routing: Different models for different requests SLA-aware: Reject rather than overload

-

Related Notes

• Continuous Batching - Foundation for efficient serving
• Pagedattention - Batching optimization
• Llm Inference Optimization - Complete inference stack
• Cost Optimization Strategies - Efficiency through good routing