Load Balancing - Algorithms (Round Robin, Least Connections, IP Hash)

▶

Steps

setup

Initialize Load Balancer State

The load balancer initializes with three servers: S1, S2, and S3. It sets the round robin index to 0, connection counts to {S1:2, S2:1, S3:3}, and marks all servers as healthy.

💡 Initialization sets the baseline state for all algorithms, showing server health and current load.

Line:

self.servers = servers
self.index = 0
self.connections = {server: 0 for server in servers}
self.healthy = {server: True for server in servers}

💡 The load balancer tracks server health and load to make informed routing decisions.

traverse

Round Robin: Select Server S1

The load balancer selects the server at index 0 (S1) for the Round Robin algorithm. It checks if S1 is healthy, which it is, so it chooses S1 and increments the index to 1.

💡 Round Robin cycles through servers in order, skipping unhealthy ones.

Line:

server = self.servers[self.index]
self.index = (self.index + 1) % n
if self.healthy[server]:
    return server

💡 Round Robin uses a rotating index to distribute load evenly among healthy servers.

traverse

Round Robin: Skip S2 if Unhealthy (Simulated)

Simulating S2 as unhealthy, the load balancer checks S2 at index 1 but finds it unhealthy, so it skips S2 and moves to the next server.

💡 Round Robin skips unhealthy servers to avoid routing requests to down servers.

Line:

server = self.servers[self.index]
self.index = (self.index + 1) % n
if self.healthy[server]:
    return server

💡 Health checks prevent routing to servers that cannot handle requests.

prune

Least Connections: Identify Healthy Servers

The load balancer filters servers to only those that are healthy. Here, all servers are healthy, so the healthy_servers dictionary includes S1, S2, and S3 with their current connection counts.

💡 Filtering healthy servers ensures only available servers are considered for least connections.

Line:

healthy_servers = {s: c for s, c in self.connections.items() if self.healthy[s]}

💡 Only healthy servers are candidates for load balancing decisions.

compare

Least Connections: Select Server S2

Among healthy servers, the load balancer finds the server with the fewest active connections. S2 has 1 connection, fewer than S1 (2) and S3 (3), so S2 is selected.

💡 Least Connections balances load by choosing the least busy server.

Line:

return min(healthy_servers, key=healthy_servers.get)

💡 Load balancing can optimize resource usage by considering current server load.

traverse

IP Hash: Compute Hash for Client IP

The load balancer computes a hash of the client IP '192.168.1.100' to determine the initial server index for IP Hash selection.

💡 IP Hash uses client IP to consistently route requests to the same server.

Line:

idx = (hash(client_ip) + i) % n

💡 Hashing client IP provides sticky sessions by mapping clients to servers.

compare

IP Hash: Check Server at Computed Index

The load balancer checks the server at the computed index (e.g., index 2 → S3). Since S3 is healthy, it selects S3 for routing the client request.

💡 IP Hash tries servers in order starting from the hash index, skipping unhealthy ones.

Line:

server = self.servers[idx]
if self.healthy[server]:
    return server

💡 IP Hash ensures consistent routing by client IP while respecting server health.

expand

Round Robin: Increment Index for Next Request

After selecting S1, the Round Robin index is incremented to 1, preparing for the next request to select the next server in order.

💡 Incrementing the index ensures even distribution over time.

Line:

self.index = (self.index + 1) % n

💡 Round Robin cycles through servers in a circular manner.

expand

Least Connections: Update Connection Count for S2

After selecting S2, the load balancer increments the connection count for S2 to reflect the new active connection.

💡 Updating connection counts keeps load balancing decisions accurate.

Line:

self.connections[server] += 1

💡 Connection counts dynamically change as requests are routed.

reconstruct

Final State: Summary of Server Selections

The load balancer has selected S1 for Round Robin, S2 for Least Connections, and S3 for IP Hash. The internal states reflect these selections and updated indices and counts.

💡 This final step consolidates the results of all three algorithms for comparison.

Line:

# Final selections returned by each method

💡 Each algorithm uses different criteria to balance load, visible in their final choices.

class LoadBalancerDetailed:
    def __init__(self, servers):  # STEP 1
        self.servers = servers
        self.index = 0
        self.connections = {server: 0 for server in servers}
        self.healthy = {server: True for server in servers}

    def health_check(self, server, status):  # STEP 3
        self.healthy[server] = status

    def round_robin(self):  # STEP 2,8
        n = len(self.servers)
        for _ in range(n):
            server = self.servers[self.index]  # select server at current index
            self.index = (self.index + 1) % n  # increment index
            if self.healthy[server]:  # check health
                return server
        return None

    def least_connections(self):  # STEP 4,5,9
        healthy_servers = {s: c for s, c in self.connections.items() if self.healthy[s]}  # filter healthy
        if not healthy_servers:
            return None
        server = min(healthy_servers, key=healthy_servers.get)  # select least connections
        self.connections[server] += 1  # increment connections
        return server

    def ip_hash(self, client_ip):  # STEP 6,7
        n = len(self.servers)
        for i in range(n):
            idx = (hash(client_ip) + i) % n  # compute index
            server = self.servers[idx]
            if self.healthy[server]:  # check health
                return server
        return None

📊

Load Balancing - Algorithms (Round Robin, Least Connections, IP Hash) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how server health, connection counts, and client IPs influence load balancing decisions, making the abstract code concrete.

Load balancer internal state initialized with servers, connections, and health.

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Initialization: servers set, connections counts assigned, all healthy

Round Robin index incremented to 1 after selecting S1

Hop: 2

Server S1

Server S2

Server S3

Load Balancer

Client

📦Packet

↗ fromLB

↘ toS1

📄 payloadRequest

🔌 protocolTCP

🚩 flags

src→Client:12345

dst→S1:80

data→Request

Round Robin: selected S1 at index 0

Round Robin index incremented, skipped unhealthy S2

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Round Robin: skipped S2 as unhealthy

Healthy servers identified for least connections selection

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Least Connections: filtered healthy servers

Least Connections chose server with minimum active connections

Hop: 2

Server S1

Server S2

Server S3

Load Balancer

Client

📦Packet

↗ fromLB

↘ toS2

📄 payloadRequest

🔌 protocolTCP

🚩 flags

src→Client:12345

dst→S2:80

data→Request

Least Connections: selected S2 with 1 connection

Computed initial index for IP Hash selection

Hop: 1

Server S1

Server S2

Server S3

Load Balancer

Client

src→192.168.1.100:—

dst→—:—

IP Hash: computed hash for client IP

IP Hash selected healthy server at computed index

Hop: 2

Server S1

Server S2

Server S3

Load Balancer

Client

📦Packet

↗ fromLB

↘ toS3

📄 payloadRequest

🔌 protocolTCP

🚩 flags

src→192.168.1.100:12345

dst→S3:80

data→Request

IP Hash: selected S3 at hashed index

Round Robin index updated for next selection

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Round Robin index incremented to 1

Connection count updated for selected server

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Least Connections: incremented connection count for S2

Final server selections completed for all algorithms

Hop: 0

Server S1

Server S2

Server S3

Load Balancer

Client

Round Robin selected S1

Least Connections selected S2

IP Hash selected S3

Key Takeaways

✓ Round Robin cycles through servers in order, skipping unhealthy ones to ensure even distribution.

This is hard to see from code alone because the index update and health check interplay is subtle.

✓ Least Connections selects the server with the fewest active connections, balancing load dynamically.

Visualizing connection counts clarifies how load balancing adapts to server usage.

✓ IP Hash uses client IP hashing to consistently route requests to the same healthy server, supporting sticky sessions.

The hashing and fallback logic is easier to grasp when seen step-by-step.

Practice

1. In which scenario is TCP's sliding window mechanism primarily responsible for controlling data transmission?

easy

A. When limiting the sender's data rate to avoid overwhelming the receiver's buffer

B. When adjusting the sending rate based on network congestion signals

C. When retransmitting lost packets after timeout

D. When establishing the initial connection handshake

Solution

1. Step 1: Understand sliding window's role in flow control

   Sliding window controls how much data the sender can send before receiving an acknowledgment, primarily to match the receiver's buffer capacity.

2. Step 2: Differentiate from congestion control mechanisms

   Adjusting sending rate based on congestion is handled by congestion control algorithms like AIMD, not sliding window.

3. Step 3: Identify retransmission and handshake roles

   Retransmissions and connection handshake are separate TCP mechanisms unrelated to sliding window's flow control.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sliding window = flow control to protect receiver buffer capacity.

Hint: Sliding window controls receiver buffer limits, congestion control manages network load.

Common Mistakes:

• Confusing flow control with congestion control
• Assuming sliding window handles retransmissions
• Mixing connection setup with data flow control

2. When a TCP packet is lost during transmission, what sequence of events occurs internally before the data is successfully received?

easy

A. The sender immediately retransmits the lost packet without waiting for any signal

B. The receiver sends an acknowledgment for the last correctly received packet, triggering retransmission after timeout

C. The receiver sends a negative acknowledgment (NAK) to request retransmission of the lost packet

D. The sender continues sending new packets without retransmitting lost ones

Solution

1. Step 1: Understand TCP reliability mechanism

   TCP uses acknowledgments (ACKs) to confirm receipt of packets.

2. Step 2: Lost packet detection

   If a packet is lost, the sender does not receive an ACK for it within a timeout period.

3. Step 3: Retransmission trigger

   After timeout, the sender retransmits the lost packet.

4. Step 4: Evaluate options

   The receiver sends an acknowledgment for the last correctly received packet, triggering retransmission after timeout correctly describes the process. The sender immediately retransmits the lost packet without waiting for any signal is incorrect because retransmission waits for timeout or duplicate ACKs. The receiver sends a negative acknowledgment (NAK) to request retransmission of the lost packet is incorrect; TCP does not use NAKs. The sender continues sending new packets without retransmitting lost ones ignores retransmission, violating TCP reliability.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   TCP relies on ACK timeouts to detect loss and trigger retransmission.

Hint: TCP retransmits after timeout triggered by missing ACKs, not immediately or via NAKs.

Common Mistakes:

• Believing TCP uses negative acknowledgments (NAKs)
• Thinking retransmission happens immediately without waiting
• Assuming sender ignores lost packets

3. What is a key trade-off when setting a very long Time-To-Live (TTL) value for cached content on CDN edge servers?

medium

A. Long TTL improves cache hit rate but increases latency for users

B. Long TTL reduces origin server load but risks serving outdated content

C. Long TTL increases origin server load due to frequent cache refreshes

D. Long TTL causes edge servers to discard content too quickly

Solution

1. Step 1: Understand TTL impact on cache freshness

   Long TTL means cached content stays longer before expiration.

2. Step 2: Effect on origin server load

   Long TTL reduces requests to origin, lowering load.

3. Step 3: Risk of stale content

   Long TTL risks serving outdated content if origin updates occur during TTL.

4. Step 4: Analyze other options

   Long TTL increases origin server load due to frequent cache refreshes is incorrect because long TTL reduces origin load, not increases it. Long TTL improves cache hit rate but increases latency for users is wrong because longer TTL improves latency by increasing cache hits. Long TTL causes edge servers to discard content too quickly is false; long TTL means content is kept longer, not discarded quickly.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Long TTL trades off freshness for reduced origin load.

Hint: Long TTL -> less origin load but stale content risk

Common Mistakes:

• Confusing TTL effects on origin load
• Assuming longer TTL increases latency
• Misunderstanding TTL causes faster cache eviction

4. Why is it generally not advisable to implement routing decisions at the Transport Layer instead of the Network Layer?

medium

A. Transport Layer does not have access to IP addresses needed for routing

B. Transport Layer is too slow to handle routing efficiently

C. Routing requires encryption which Transport Layer cannot perform

D. Transport Layer only manages physical connections, not logical routing

Solution

1. Step 1: Understand routing requirements

   Routing decisions depend on logical addressing (IP addresses) handled at the Network Layer.

2. Step 2: Role of Transport Layer

   Transport Layer manages end-to-end communication using ports, not IP addresses, so it lacks necessary info for routing.

3. Step 3: Why other options are incorrect

   Transport Layer speed is not the main limitation; encryption is unrelated to routing; physical connections are handled by lower layers.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Transport Layer lacks IP address info for routing [OK]

Hint: Routing needs IP addresses, which Transport Layer doesn't handle [OK]

Common Mistakes:

• Assuming Transport Layer handles routing because it manages connections
• Confusing encryption with routing
• Believing Transport Layer manages physical connections

5. Which of the following statements about the scalability and overhead trade-offs between Distance Vector and Link State routing is TRUE?

medium

A. Distance Vector routing scales better in large networks because it floods link state advertisements less frequently

B. Distance Vector routing has lower convergence time but higher memory usage compared to Link State

C. Link State routing requires more memory and CPU but scales better due to faster convergence and less routing loops

D. Link State routing uses less bandwidth overall because it only sends updates when topology changes

Solution

1. Step 1: Understand resource usage

   Link State routing stores the entire network topology, requiring more memory and CPU for Dijkstra's algorithm.

2. Step 2: Analyze scalability and convergence

   Link State converges faster and avoids routing loops better, making it more scalable despite higher resource use.

3. Step 3: Evaluate options

   Distance Vector routing scales better in large networks because it floods link state advertisements less frequently is false because Distance Vector does not flood link state advertisements at all. Distance Vector routing has lower convergence time but higher memory usage compared to Link State is false because Distance Vector generally has slower convergence and lower memory usage. Link State routing uses less bandwidth overall because it only sends updates when topology changes is misleading; Link State floods updates on topology changes, which can be bandwidth intensive.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Link State trades higher resource use for better scalability and convergence.

Hint: More CPU/memory but faster convergence -> Link State scales better

Common Mistakes:

• Assuming Distance Vector floods updates like Link State
• Confusing convergence time and memory usage
• Believing Link State sends fewer updates overall