This paper investigates the stochastic property of the packet destinations and proposes an address generation algorithm which is applicable for describing various Internet access patterns. We assume that a stochastic process of Internet access satisfies the stationary condition and derive the fundamental structure of the address generation algorithm. Pseudo IP-address sequence generated from our algorithm gives dependable cache performance and reproduces the results obtained from trace-driven simulation. The proposed algorithm is applicable not only to the destination IP address but also to the destination URLs of packets, and is useful for simulation studies of Internet performance, Web caching, DNS, and so on.

This paper investigates the stochastic property of packet destinations in order to describe Internet access patterns. If we assume a sort of stationary condition for the address generation process, the process is an LRU stack model. Although the LRU stack model gives appropriate descriptions of address generation on a medium/long time-scale, address sequences generated from the LRU stack model do not reproduce Zipf-type distributions, which appear frequently in Internet access patterns. This implies that the address generation behavior on a short time-scale has a strong influence on the shape of the distributions that describe frequency of address appearances. This paper proposes an address generation algorithm that does not meet the stationary condition on the short time-scale, but restores it on the medium/long time-scale, and shows that the proposed algorithm reproduces Zipf-type distributions.

This paper proposes the Dual Zipfian Model addressing how to describe HTTP access trends in large-scale data communication networks, and discusses how to design the capacity of address cache tables in an edge router of the networks. We show that destination addresses of packets can be characterized by two types of Zipf's law. Fundamental concept of the Dual Zipfian Model is in complementary use of these laws, and we can derive the relationship between the number of accesses and the number of destination addresses. Experimental results show that the relation gives a good approximation. Applying this relation, we derive cache hit probabilities of the address cache table that incorporates high-speed address resolution. Using the probabilities, design issues including the capacity of the cache tables and aging algorithms of cache entries are also discussed.