Craig Partridge, BBN

Position Statement for
NSF Workshop on Internet Statistics Measurement and Analysis

LOCALITY AND ROUTE CACHES

There's been a certain amount of contradictory information about whether there is enough traffic locality, particularly in backbone routers, to make route caches useful. I'm interested in experiments that help directly answer this question and help us identify likely cache hit rates for various cache sizes. I recently redid Dave Feldmeier's experiment on router cache hit rates using a trace from FIX WEST. I presented these at the SDSC workshop on traffic statistics this week and though they might interest E2E.

The table is below. The data was from a 5 minute trace and I took two types of measurements. One (labelled "hit rate") is the (32-bit IP destination-address) cache hit rate achieved by starting with an empty cache and running through all 5 million packets. The second ("avg hit rate per 100K") is the average hit rate if the cache is reset every 100K packets (as it might be by routing table changes). The numbers on the far right are from DCF's 1988 study (note that he preloaded the cache before starting to measure hit rates and his backbone numbers are for MIT's external link, which isn't quite the same as being the backbone proper).

A couple of random thoughts as you read. Even modest hit rates can be very effective in improving performance (as little as a 10 to 20% hit rate can, in some situations, be helpful). Also, the network is about 100 times bigger in networks (probably more in hosts) since the 1988 study and the traffic intensity was about 600 times higher (i.e. 600 times as many packets per unit time). While two points aren't enough to measure, there's some hint that the needed cache size is scaling linearly with increases in the number of destinations or amount of traffic.


FIX WEST Trace of Mon, 9/25/95 at 17:15PM. 4.97 Mpackets, 31.9 thousand total destinations seen
cache size avg hit rate rate/100K Feldmeir 1988 result
1 0.0180 0.2083
10 0.0938 0.0938 0.8143
20 0.1343 0.1343 0.9252
50 0.2218 0.2218
100 0.2952 0.2952
500 0.5001 0.4994
1000 0.6090 0.6072
2000 0.7736 0.7677
5000 0.9325 0.9128
10000 0.9740 0.9340