Explore BrainMass

URL hashing to caches

Suppose an institution has four caches, referred to as cache-0, cache-1, cache-2 and cache-3. Suppose that the URL hashing scheme operates as follows:
(1) only the host name of the URL is used.
(2) all non-alphabetic characters are ignored.
(3) each alphabetic character is assigned a number corresponding to its position in the alphabet.
(4) these numbers are added modulo 4 to get the hash value of the URL.
(5) if the hash value is 0, the request is directed to cache-0; if 1, the request is directed to cache-1; if 2, the request is directed to cache-2; if 3, the request is directed to cache-3.
For example, the URL has hash value 1 + 1 + 1 + 2 + 2 + 2 + 3 +15 + 13(modulo 4) = 0; a request for this URL is sent to cache-0.

[a] Determine to which caches requests for each of the following URLs will be directed:;;;;;

[b] Suppose the institutional caches are initially empty. During the first morning of operation, the requests from users at the institution include,,, During the afternoon of the same day, there are seven requests to each of these URLs. Which servers (origin and cache servers) will satisfy these 32 requests?

[c] Suppose now on the second day of operation a fifth cache is added, cache-4 and the algorithm in the browsers is changed to calculate the hash value using modulo 5 rather than modulo 4. Suppose now requests are made for the same six URLs listed in Part a of this problem. What will happen?

Solution Preview

[a] Answer to this part is organized in group of three lines (URL, Hash value, Cache used) for each case. "Cache used" is used to mean the same as "Cache to which the request for URL is directed to".

Hash value = 23+23+23+15+8+5+3+1+13+16+21+19+3+15+13 (modulo 4) = 1
Cache used = cache-1

Hash Value = 23+23+23+12+9+22+1+3+21+11 (modulo 4) = 0
Cache used = cache-0

Hash Value = ...

Solution Summary

Solution shows hash value computation for each URL in [a] and [c], in order to determine the cache to which the request for that URL will be directed.