Load balancing at front node of each cluster

First front node collects information about request rates from each client IP, then periodically it sends request rate information of only those clients which have high request rate to DNS.

Similar to DNS, front node also receives different types of messages and invokes appropriate message handler based on type of message, main messages are server load information and client request rate from each servers in cluster, request for measuring RTT to client from DNS and it also selects server in cluster for each new TCP connection from client and rewrites destination address of IP packets coming from clients with selected address.

Each server periodically (at large intervals of order of minute) sends request rate information of clients in terms of number of requests by that client. On receipt of request rate update message, receive_request_rate procedure is invoked.

procedure receive_request_rate
{
 Input: Client IP addresses, requests 
 Output: None
 
 for each Client IP address
    update_request_rate(Client IP,number of requests)

 update global request rate information
}

update_request_rate creates new record or finds record for given client IP and aggregates request rate information about each client.

Periodically cluster sends aggregated request rate information of clients which generate high number of requests than average client.

procedure send_request_rate
{
 Input: Client IP and their request rates
 Output: None (sends this info to DNS)

 calculate Threshold based on average request rate

 for each Client IP having request rate > Threshold{
    add Client IP and request rate in queue
    if(queue is full)
        send queued request rate information of clients to DNS
 }	
 send queued request rate information of clients to DNS
}

Front node receives detailed load information from each server periodically. Using average number of connections sent to it in that predefined interval and obtained load information from server, front node estimates number of connections server can serve, i.e. capacity of server. This estimate is updated with every load update from server.

procedure receive_server_load
{
 Input: Server IP address, load
 Output: None

 find record for server using IP address and update server load
 estimate and update number of connection server can serve
 update cluster's load information and available capacity
}

Cluster sends aggregated load information periodically to server or when load condition changes significantly.

When DNS requests for measuring RTT between client and Cluster, following procedure is executed.

procedure receive_probe_for_rtt
{
 Input: Client IP addresses
 Output: None 

 for each Client IP address in list
      send predefined number of echo requests to client periodically 
}

Clients reply with Echo reply for each echo request, RTT is measured and averaged. Average RTT along with number of successful probes are sent to DNS periodically.

Finally it forwards requests to servers in cluster in proportion to remaining capacity of each server,

procedure forward_request
{
 Input: IP packets from clients for HTTP request
 Output: IP packets with destination address of selected server

 if(connection already exists for this client IP and port){

     if(packet is fin)
           move this connection record to a list where it will be recycled after few 
           minutes
     
     update time stamp for this connection
     write IP address of server in destination field and re inject on network
 }
 else if(packet is syn){
       select servers in proportion to their remaining capacity
       create new connection record with current time stamp
       write IP address of server in destination field and re-inject on network
 } else
          drop this packet	
 
 if(load on each server > capacity and least loaded cluster list not empty)
        redirect request to other clusters in proportion to their free capacity
}

All the connection records for connection on which there was no packet transmitted from source for a long time are also freed periodically.