PERFORMANCE EVALUATION OF URL ROUTING: FOR CONTENT DISTRIBUTION NETWORKS
Zornitza Genova Prodanoff, Kenneth J. Christensen · 2009
As the World Wide Web continues to grow in size, content is being co-located throughout the world in Content Distribution Networks (CDNs). These CDNs need entirely new methods of distributing client requests. The idea of a URL router has been introduced and in this dissertation the performance of URL routing is addressed. A URL router that uses HTTP redirection to automatically forward requests is architected. Significant open problems are finding effective ways to (1) reduce the size of the routing table, and (2) perform fast routing look-ups. These two problems must be solved in order for CDNs to become fully viable and thus are of significant interest. The first problem is solved by proposing the use of CRC32 as a means of reducing the length of a URL (typically 50 bytes) to a four-byte signature. The CRC32 method is shown to require less CPU resources, generate equal or smaller size digests, achieve equal collision rates, and simplify switching when compared to existing MD5-Bloom and CRC19 methods. The second open problem is solved by a new “Aggressive” hashing algorithm. The average look-up time performance of Aggressive hashing is compared to that of simple chain hashing and self-adjusting H1 hashing. Aggressive hashing outperforms in look-up time simple chain hashing by a factor of 16 and H1 by a factor of about two. A major contribution of this dissertation is studying the queueing behavior of hashing algorithms. A simulation model was designed as a single server queueing system where the arrival rate is determined by an HTTP trace and the service time by hash table look up. For a constant throughput, the new Aggressive hashing method exhibits 27 times shorter mean queue length than simple chain hashing and about two times shorter than H1 hashing. For constant utilization, the results were surprising in that H1 and Aggressive result in several magnitudes difference in mean queue length. The isolated cause for this counter-intuitive result is the high level of autocorrelation in the H1 hashing look-up time. In conclusion, CRC32 URL signatures and Aggressive hashing are the best methods for designing the next generation of URL routers to enable future growth of the Internet.