Round-robin Policy

Round-robin is a slightly more advanced policy. Given a list of replica addresses, it also sequentially takes as many as needed, but diversifies its responses by starting at subsequent addresses each time. After reaching the end of the list, round-robin moves to its beginning, and so on, thus implementing a circular list. Additionally, after each query, it rotates the list by one address, so that the address now returned as second will be the first next time, and so forth (see Figure 4.2).

Figure 4.2: The round-robin policy uses a circular list of addresses

The simple idea of using a circular list of addresses makes round-robin much more powerful than the static name-to-address mapping. In theory, if 1000 clients came to use a service that has 10 replicas, each of the replicas would service 100 of them (assuming that each client contacts the first replica in the list of addresses it obtains). Therefore, it seems that round-robin provides simple load balancing. Practice shows, however, that it is not that easy. The problem lies in DNS response caching. Imagine what happens to the response that the redirector generates. As long as we use non-zero TTL values, a response will be cached on at least one DNS server somewhere in the world. Until the response expires, the DNS server will give it to anyone that needs it. As a consequence, all the clients of the DNS server will be (re)directed to a single replica. In this way the load balancing we implement is dependent on the number of clients that ask each DNS server for the replica addresses. This problem is known as a hidden load factor problem and has no satisfactory solution so far [7,12].

For our purpose, restricting the redirector to use round-robin only is unacceptable. Since round-robin does not consider the client location when generating a response, it cannot be used to redirect clients to ``their'' replicas. It is still useful, however, to support this policy. Although the round-robin load balancing is imperfect, it may turn out to be good enough for some applications.