Load balancing at DNS

In response to query from client for resolving domain name, DNS returns IP address of server. All requests are sent to server having that IP address for time period called Time to live (TTL). After expiration of TTL, query is once again sent to DNS. Since within TTL period all requests from that client (or its gateway) are sent to the same server, if number of request generated by that client are higher than others it can create load skew. Aim should be to assign clients having high request rates to servers having higher capacity. Again TTL value should be small because load skew is created by these clients.

For getting request rate (number of requests in unit period), servers (or front nodes of clusters) should send this information periodically to DNS. We distinguish between clients based on their request rates. Servers send information of request rate only when client request rate is higher than a threshold. DNS instructs few possibly nearest clusters (having remaining capacity higher than request rate) to get round trip delay to client.

For clients having high request rate, we maintain information about their request rate, list of few candidate servers(say 3) having enough remaining capacity at time of RTT probe with RTT, time stamp of last RTT probe.

Procedure recvmsgs is procedure responsible for receiving messages of different types and dispatching these messages to appropriate handler functions depending on type of message, pseudo code below shows main messages received :

procedure recvmsgs
{
 Input: Socket for receiving messages
 Output: None

 read message from socket and determine type of message
 
 switch(message type){
        case load_info:
        /* Message from front nodes about load information on each cluster */
            call update_load 
            break;
        case request_rate:
        /* Message from front nodes about request rate of clients */
            call update_requestrate
            break;
        case ip_request:
        /* Message from DNS for preferred IP address of client */
            call resolve_ip
            break;
        case rtt_reply:
        /* Message from front nodes about RTTs between cluster and clients */
            call update_rtts
            break;            
}

Procedure update_request_rate is called when front node sends this request rate information to DNS.

procedure update_request_rate
{ 
 Input: Client IP addresses, request rate
 Output: None

 for each IP address of client (or its gateway) {
    if(no request rate available for this IP)
       add request rate record for this client with current time stamp
    else
       update request record for this client with current time stamp
    
    if(no candidate server in list or time stamp of probe is too old)
        send_probes_for_rtt(Client IP)
 }
	
 update average request rate information.
}

If no request rate information about a client IP is received for few periods of request update then that entry is deleted.

Procedure send_probes_for_rtt adds IP address of client for sending probe for measuring rtt to list of new nearest and not overloaded clusters.

procedure send_probes_for_rtt
{
 Input : IP address of client to probe
 Output: None

  select few clusters nearest (approximated using IP address) to client having 
  remaining capacity > request rate of client
  
  for each cluster in above list
          add client IP for sending request for rtt probes for this cluster
  
  update probe timestamp for client with current time
}

Actual message containing Client IP addresses is sent to each cluster periodically after every fixed interval or sufficient number of clients are already queued.

Procedure update_rtts is executed when message from cluster front node about information of round trip time between them and client is received.

procedure update_rtts
{
 Input: Cluster IP, Client IP, rtt, number of successful rtt probes
 Output: None

 if(number of candidate servers is less for Client IP)
      add_candidate(Client IP,Cluster IP,rtt,num probes)
 else if(any candidate server has higher rtt in candidate server list 
         or had less number of successful probes)
      update_candidate(Client IP,Cluster IP, rtt, num probes)  
	
}

add_candidate and update_candidate keep a list of rtt records in ascending order of round trip time and number of successful rtt probes for given client IP.

Procedure update_load is executed when message from front node of any cluster about load information is received.

procedure update_load
{
 Input: IP address of cluster's front node, capacity, load
 Output: None
	
 find record for node
 update load information of cluster
 update available free capacity of cluster and whole system
}

Finally clients request for host name to IP address resolution.

procedure resolve_ip
{
 Input: IP address of client (or its gateway, i.e. firewall etc.) and domain name
 Output: IP address of front node of cluster

  if (information about client request rate is available){
      if(probe time stamp is too old)
             send_probes_for_rtt(client IP)
	 
      find list of clusters sorted on previously probed rtt to client
      for each cluster in list in ascending order of rtt
         if(available capacity of cluster > request rate of client){ 
                 reduce available capacity of cluster by client request rate
                 return(Cluster IP address);
         }
      /* If all servers probed are overloaded */
      send_probes_for_rtt(client IP)
  }	
  else{
        set request_rate to average request rate of all clients. 
        find list of nearest clusters sorted on nearness approximated by IP address
        for each cluster in list in ascending order of proximity     	
           if( available capacity of cluster > request rate of client){
               reduce available capacity of cluster by client request rate
               return(Cluster IP address);
           }
  }
  /* If no cluster is yet selected, all servers are overloaded */
  select cluster in proportion to free capacity
  return(Cluster IP address)	
}