IEICE TRANS. COMMUN., VOL.E84–B, NO.8 AUGUST 2001

2142

PAPER

Special Issue on Internet Technology

Stochastic Model of Internet Access Patterns∗
Masaki AIDA† and Tetsuya ABE†† , Regular Members

SUMMARY This paper investigates the stochastic propertyof 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 satisﬁes 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 fromtrace-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.
key words: Internet, stochastic process, destination address,
LRU stack, caching1.

Introduction

The Internet system is made of many queueing andcaching mechanisms. They are hierarchically conﬁgured in protocol layers or their time-scales and are mutually related. In addition, these complicated situations
inﬂuence the quality of service (QoS) and the performance of systems. In this situation, computer simulations and experimental test-beds probably are powerfulapproaches to evaluate QoS and Internet performance.
These approaches require a pseudo traﬃc generator which is based on a traﬃc model of Internet accessbehavior. Interarrival distribution of the packets andpacket length distribution are a signiﬁcant part of thetraﬃc model. They have been investigated in [1], [2].
The other signiﬁcant part of the traﬃc model is theassignment of the appropriate destination address to apacket generated at a pseudo traﬃc generator. Thisis because the cache performance is strongly inﬂuenced
from the diversity of the destination addresses of thepackets.
The fact that computer memory references exhibit
locality behavior is now well established [3]. Raj Jain
reported that the frames on computer networks also
exhibit the locality behavior [4]. Since the cache performance is inﬂuenced by the locality behavior, the locality behaviors of the packets are important for evalManuscript received January 23, 2001.
Manuscript revised March 15, 2001.
†
The author is with NTT Information Sharing Platform
Laboratories, Musashino-shi, 180-8585 Japan.
††
The author is with NTT EAST R&D Center, Tokyo,163-8019 Japan.
∗
A part of this paper was presented at IEEE INFOCOM
2001 [19].

uating Internet performance. In general, the comparison among performances of the diﬀerent caching mechanisms are conducted through trace-driven simulations[4]–[6]. Trace-driven simulation uses logs of actual Internet accesses as an input traﬃc of the simulation.
Hence, we can reproduce the situation of the speciﬁc
network traﬃc by using the trace-driven simulation,
but cannot obtain information about the other typesof networks.
This paper investigates stochastic property of thedestinations of packet and proposes an address generation algorithm which is applicable for describing various
Internet access patterns. We assume a stochastic process of Internet access satisﬁes a sort of the stationary
condition and derive the fundamental structure of theaddress 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, Webcaching, DNS, and so on.
2.

Preliminary

2.1 Notations and Deﬁnitions
Internet access behaviors include similar issues in computer memory access patterns. We, therefore, prepare
the framework for Internet access models, using wellknown notions in computer memory access models.
Time t is incremented to t + 1 when an access occurs, and t = 0, ±1, ±2, . . ..
• working set: W (t, τ )The set whose elements are distinct addresses generated during a period [t − τ, t) (i.e., {t − τ, t −τ + 1, . . . , t − 1}). In case for τ < 0, the period is(t, t − τ ].
• working set size: w(t, τ )Size of a working set W (t, τ ), i.e., the number of
elements of W (t, τ ).
• inverse stack growth function (ISGF) [3]: f (t)Expectation value of the number of distinct addresses generated during a period (t, t + τ ],f (t, τ ) := E[w(t, −τ )].

(1)

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

2143

In addition, stack growth function (SGF), g(t, k),denotes the expectation value of the number of accesses such that the number of distinct addresses
is k, i.e.,f (t, τ ) = k↔

g(t, k) = τ,org = f −1 .

(2)
(3)

Note that because ISGF f is deﬁned only on integer,
SGF g cannot be deﬁned directly. The consistent way
to obtain the relation between ISGF and SGF is shownin [3]. Hereafter, we regard ISGF and SGF as functions
deﬁned on the real number with respect to τ and k,
respectively.

the performance of the address cache is an essential
object [4], [7]. Cache performance strongly depends on
locality of Internet accesses. Because IRM cannot take
locality into account, it is an insuﬃcient model for Internet access modeling.
Since we can evaluate cache performance if ISGF,
f , is given [7], ISGF and WS models are important.
Hereafter, from natural and basic assumptions on ISGF
and investigation of the working set, we show that theaddress generation probability must obey an LRU stackmodel. In addition, we show the relationship between
the address generation probability ak and ISGF f .
3.

Basic Structure of Address Generation
Probability

2.2 Reference Models for Computer Memory

3.1 Assumption

In computer memory references, it is well known thatthe concept about locality of a reference pattern appears. The locality (especially, temporal locality) implies a high probability of reuse. A similar concept also
appears in Internet access [4].
This subsection reviews typical memory reference
models arranged for Internet access models [4].

We assume the following property of ISGF.

• independent reference model (IRM)
This model assumes accesses are independent. The
probability that a new access has address i is determined by the address i (and the probability isdenoted as pi ). Accessed address sequence is generated by i.i.d. and the distribution pi . Because
recently accessed addresses do not give any information about the next accessed address, IRM cannot capture locality.
• working set model (WS model) [8]This model assumes that the addresses accessed in
the last accesses are highly likely to be accessed.
The WS model, therefore, captures locality. Theintervalis called the working set window size.
For a given working set window size , the smaller
working set size w(t, ) means stronger locality.
• least recently used (LRU) stack model [9]An LRU stack is a list of addresses sorted in orderaccording to the times of their most recent access.
So, the most recently accessed address is at the
top of the stack and the least recently accessed
address is at the bottom. The probability that the
newly accessed address is the same as the address
at k-th position in the LRU stack is determinedby position k, and its probability is denoted as ak .
Usually, ak decreases with respect to increases in
k. Because the most recently accessed address isat the top of the LRU stack, the probability thatthe next accessed address is the same is high. The
LRU stack model, therefore, captures locality.
In performance evaluation of address resolutions,Time-translation invariance:
ISGF f (t, τ ) is independent of the time t which
denotes time when we start to measure address
generation. For any t, s,f (t, τ ) = f (s, τ ).

(4)

From this assumption, we denote f (τ ) := f (t, τ ).
Validation of time-translation invariance is discussed in
Sect. 5 through experimental data.
In queueing models, the typical and usual traﬃcmodel as an input is described by a stationary stochastic process. On the other hand, the notion of a stationary process of address generation is not well-deﬁned yet.
However, it is natural to accept that if the address generation process is stationary, the ISGF should have atime-translation invariance. Thus, the time-translation
invariance should be, at least, a necessary condition of
the stationarity. We assume it in order to produce astationary process of the address generation.
Incidentally, we can consider other possibilities
for the stationarity condition. For example, we may
adopt the assumption that the working set size distribution [10],p(k, τ ) := Pr{w(t, τ ) = k},(5)

is independent of t. Although this seems to bea stronger stationarity condition than the timetranslation invariance of ISGF f , stationarity of (5)is obtained from (4) as a result. This is because theassumption (4) completely determines the fundamental structure of the address generation algorithm, as
shown in the following sections.
3.2 Time-Reversal Invariance
Let us consider f (−τ ). This means the expectation

IEICE TRANS. COMMUN., VOL.E84–B, NO.8 AUGUST 2001

2144

value of the number of distinct addresses generated in
the period which is from a time t until the past timet − τ through the backward direction of time. By using
the time-translation invariance (4), we have the timereversal invariance for ISGF,
f (−τ ) = f (t, −τ )= f (t − τ − 1, τ )= f (τ ).

(6)

3.3 Address Generation Probability
We consider three adjacent periods A, B, and C(Fig. 1). Let the sets of distinct addresses generated inthese periods, i.e., working set, be W (A), W (B), andW (C), respectively. Figure 2 denotes Venn’s diagramof these working sets.
Here, we focus on the subset W ∗ whose elements
are also elements of both W (A) and W (C), but are notelements of W (B), i.e., the hatched part in Fig. 2,∗

W := {W (A) ∩ W (C)} \ W (B).

E [|W ∗ |] = {f (−(n + 1)) − f (−n)}− {f (−(n + m + 1)) − f (−(n + m))}= {f (n + 1) − f (n)}− {f (n + m + 1) − f (n + m)}. (10)The physical meanings of E [|W ∗ |] are as follows. |W ∗ |is 1 only when the address X generated at a time (period C) is not in W (B) but in W (A). Otherwise, |W ∗ |is 0. Thus, |W ∗ | is a random variable and can be denoted using indicator function 1{·} by|W ∗ | = 1{X ∈ W (B), X ∈ W (A)}.
∗The size of W is obtained as

E [|W ∗ |] = Pr{X ∈ W (B), X ∈ W (A)}.

E [|W ∗ |] = {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k} .

(13)Equation (13) means the probability that the newly
accessed address, X, is identical with the k-th mostrecently accessed address.

(8)

Address generation probability:
Here, we deﬁne ak as
ak := {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k} .

(14)This means that the probability that X is identical with the most recently accessed address is a1 ,the probability that X is identical with the 2nd
most recently accessed address is a2 , . . ., and theprobability that X is identical with the k-th mostrecently accessed address is ak . In other words, address generation must obey the LRU stack model
whose probability is (14).

|W ∗ | = {w(t, n + 1) − w(t − 1, n)}− {w(t, n + m + 1) − w(t − 1, n + m)}.
(9)Time intervals A, B and C.

(12)

Next, we choose n such as f (n) = k − 1 (k =1, 2, . . .) and choose m such as f (n + m) = k. Substituting n = g(k − 1) and n + m = g(k), (10) gives

We can choose m, n and 1 accesses as the periods A,
B, and C, respectively (Fig. 3). Then we have

Fig. 1(11)∗

Therefore, E [|W |] means the probability of |W | = 1,

(7)∗

|W ∗ | = |{W (A) ∩ W (C)} \ W (B)|
= {|W (B) ∪ W (C)| − |W (B)|}− {|W (A) ∪ W (B) ∪ W (C)|− |W (A) ∪ W (B)|} .

Applying the time-reversal invariance, we haveIf {ak ; k = 1, 2, . . .} is the probability, ISGF f
must satisfy ak ≥ 0 and∞

ak = 1,(15)

k=1that is, {f (g(k) + 1) − k} is monotonously decreasing
with respect to increases in k (= 0, 1, 2, . . .) and satisﬁes
lim {f (g(k) + 1) − k} = 0.

k→∞Fig. 2(16)

Venn’s diagram of working sets.

4.

Fig. 3This section shows an address generation algorithm byapplying the results of the above section. The proposed
algorithm gives a pseudo-address sequence, a sequenceof integer.

Time intervals.

Address Generation Algorithm

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

2145= f (g(m) + 1) − m.
4.1 Address Generation Procedure
We deﬁne the generative LRU stack vector L(i, m) as
follows. At the time immediately before i-th (i =0, 1, 2, . . .) address generation, we denote the most recently accessed address as x1 , the 2nd most recently
accessed address as x2 , . . ., and the k-th most recently
accessed address as xk . Then
L(i, m) := {x1 , x2 , . . . , xm }.

(17)Here, the number of components of L(i, m), m, is called
the depth of L(i, m). Initially, the depth is chosen as
0, i.e., m = 0 for L(0, 0). Then m means the numberof distinct address generations.
Let Xi denote the address of the i-th access. Address sequence {Xi ; i = 0, 1, 2, . . .} is generated by thefollowing procedure.
1. Initially, we choose X0 = 1, L(1, 1) = {1} andi = 1.
2. Determine the number j as a realization of the i.i.d.
random variable J which obeys the distribution
Pr{J = k} = ak(k = 1, 2, 3, . . .),(18)

Equation (22) is valid for all m (m = 0, 1, 2, . . .). The
probability of a brand-new address generation depends
only on the depth of the generative LRU stack vector.
Because the same depth gives the same probability, bm
is independent of the time when we start to measure address generations. Thus, the address sequence obtained
from our algorithm reproduces the time-translation invariance of ISGF.
Let us consider the time that the depth m of thegenerative LRU stack vector L(t, m) is incremented tom + 1. Because the time obeys a geometrical distribution, the mean time is 1/bm . Therefore, SGF g is
obtained asg(k) =(19)

and update L(i+1, m+1) and increment i ← i+1.
Return to 2.
4. For the depth m of L(i, m), if m ≥ j, then assign
the address of new access as
X i = xj ,(20)

and update L(i + 1, m) and increment i ← i + 1.
Return to 2.
Because the number j can be obtained using a binary
search algorithm, high-speed address generation is possible.
4.2 Reproduction of the ISGF Behavior
When the depth of the generative LRU stack vector
L(t, m) is m at a time t, we consider the probability
that the working set size w(t, n) increases, i.e.,
bm := Pr{w(t+1, n+1) = m+1| w(t, n) = m}.(21)This means the generation probability of a brand-new
address which does not exist in L(t, m). So, it is obtained as
bm =

∞

k=m+1

ak

k−1


1
.
b
m=0 m

We deﬁne the slope of f as the diﬀerencef (g(m) + 1) − f (g(m))
∆f 
:=
∆g m
(g(m) + 1) − g(m)= bm .

(23)(24)

From (23), we haveby using (14).
3. For the depth m of L(i, m), if m < j, then assign
the address of new access as
Xi = m + 1,

(22)

g(k) =

k−1

m=0

 −1
∆f 
.
∆g m

(25)

This means the address sequence obtained from the
proposed algorithm reproduces ISGF, f .
5.

Working Set Size Behaviors of Internet Accesses

In order to obtain pseudo-address sequence by using the
proposed algorithm in practice, it is necessary to determine ISGF f . In this section, we investigate asymptotic
property of working set size behaviors of Internet accesses from experimental data, and show that a powerlaw is widely applicable. Simultaneously, validation of
the time-translation invariance is discussed.
In most cases, it is well known that the destination addresses or URLs are characterized by Zipf-type
distributions [7], [5]–[11] (strictly, parts of them are
Lotoka-type distributions [12]). Here, an example of
the Zipf-type distribution is appears in the later section(see Sect. 7 and Fig. 8(a)). Although, in some cases, we
can calculate ISGF by using Zipf-type distribution [7],[13], it is not always feasible. Therefore, it is required
to determine ISGF from generally applicable property
with respect to Internet accesses.
5.1 Working Set Size Behaviors and Time-Translation
Invariance of ISGF
As an example of access networks of the Internet,

IEICE TRANS. COMMUN., VOL.E84–B, NO.8 AUGUST 2001

2146(a) For the destination IP addresses (NTT labs.
(Atsugi), Nov. 1996).

(b) For the destination URLs (NTT labs. (Atsugi),
Nov. 1996).

(c) For the destination IP addresses (NTT labs.
(Atsugi), March 1997).

(d) For the destination URLs (NTT labs. (Atsugi),
March 1997).

(e) For the destination IP addresses (NTT labs.
(Yokosuka), March 1997).

(f) For the destination URLs (NTT labs.
(Yokosuka), March 1997).

Fig. 4

Working set size behaviors of destinations (NTT labs.).

we investigate access logs of a proxy server at NTT
Laboratories. Logs are for 15 successive days. Figure 4(a) shows the relationship between working set
size, w(t, −τ ), and the number of accesses, τ , for thedestination IP addresses in log-log scale, where logs
were obtained from NTT Labs. (at Atsugi, Japan,
in Nov. 1996). Each line indicates w(t, −τ ) for t =0, 1.2 × 105 , and 2.4 × 105 , respectively. Similarly,

Fig. 4(b) shows the relationship between working set
size, w(t, −τ ), and the number of accesses, τ , for thedestination URLs in log-log scale, using the same logs.
Figures 4(c)–(f) show the similar relationships, wherelogs were obtained from NTT Labs. (at Atsugi, in
March 1997) and NTT Labs. (at Yokosuka, Japan, in
March 1997), respectively. Each ﬁgure shows w(t, −τ )is independent of t for large τ . From the law of large

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

2147(a) For the destination IP addresses (NLANR,
July 30, 1999).
Fig. 5(b) For the destination URLs (NLANR, July 30,1999).

Working set size behaviors of destinations (NLANR).

the origination IP addresses in log-log scale. Each line
indicates w(t, −τ ) for t = 0, 1.2 × 106 , and 2.4 × 106 , respectively. This ﬁgure also implies the time-translation
invariance of ISGF, at least in the asymptotic region,τ  1.
5.2 Asymptotic Power Law
From the above graphical observations, we can recognize that f (τ ) satisﬁes a power law with respect to τfor τ  1,
f (τ )  τ αFig. 6 Working set size behaviors of originations (NTTDIRECTORY, Oct. 1997).

number, asymptotic behavior of the working set size
can be related to the behavior of ISGF, asw(t, −τ ) ∼ f (t, τ )(τ  1).

(26)

Thus, these ﬁgures imply the time-translation invariance of ISGF, at least in the asymptotic region, τ  1.
As an example of backbone networks of the Internet, we investigate access logs of a cache server
at NLANR [14]. Logs are for July 30, 1999. Figure 5(a) shows the relationship between working set
size, w(t, −τ ), and the number of accesses, τ , for thedestination IP addresses in log-log scale. Each line indicates w(t, −τ ) for t = 0, 2 × 105 , and 4 × 105 , respectively. Similarly, Fig. 5(b) shows the relationshipbetween working set size, w(t, −τ ), and the number ofaccesses, τ , for the destination URLs in log-log scale.
These ﬁgures also imply the time-translation invarianceof ISGF, at least in the asymptotic region, τ  1.
As an example of WWW servers of the Internet, weinvestigate access logs of a directory site, NTT DIRECTORY [15]. Logs are for 31 successive days in October
1997. Figure 6 shows the relationship between working
set size, w(t, −τ ), and the number of accesses, τ , for(τ  1),(27)

where α is a constant. A similar property is known incomputer memory access [3]. This property is widely
applicable, e.g., for access networks, backbone networks, at a WWW server, and for the destination IP
addresses and URLs.
6.

Address Generation Algorithm Using Power
Law

This section investigates pseudo-address generation by
applying the power law of ISGF.
6.1 Address Generation Probability
We assume the asymptotic power law for f (n) is applicable for all n, i.e.,f (n) = nα .

(28)Then, address generation probability (14) is obtainedas
ak = ((k − 1)1/α + 1)α − (k − 1)(29)
− (k1/α + 1)α − k .
Because ak > 0 andIEICE TRANS. COMMUN., VOL.E84–B, NO.8 AUGUST 2001

2148
∞


ak = 1 − lim



k→∞

k=1

(k1/α + 1)α − k



=1

PL =
(30)

for 0 < α < 1, {ak ; k = 1, 2, . . .} is probability. The
asymptotic behavior of ak is expressed asak = (1 − α) k−1/α(k  1).

(31)

6.2 Time-Translation Invariance and Asymptotic
Power Law
Using power law (28), the probability that the working
set size increases, (22), is expressed as
∞


bm =


=

(m

1/α



+ 1) − m .
α(32)Using the asymptotic behavior of bm ,bm = α m−(1/α−1) + O(m−(2/α−1) ),(33)

and (23), we haveg(k) =

k−1

m=0


1 1/α−1+ O(m−1 ) .
m
α

(34)

Therefore,
lim

k→∞

1
log g(k)
= .
log k
α

(35)

This means the address sequence obtained from our algorithm reproduces the asymptotic power law of ISGF,
f (n) = nα7.

(n  1).

(36)

Experimental Results

In order to verify the eﬀectiveness of our algorithm described in Sect. 4, we compare the cache miss ratios.
We show the cache miss ratio which is obtained fromsimulation with address sequences generated by our algorithm as input, and compare it with the results oftrace-driven simulation and theoretical values.
As shown in [7], theoretical values of cache missratio, for LRU and FIFO, are obtained through the following formulae. For LRU cache, the cache miss ratio,
PL is given by
PL =

1
,
g(k + 1) − g(k)(37)

where k denotes the capacity of the cache (the numberof address entries). Applying the power law (28), we
have

(38)

Incidentally, for k  1, (38) is evaluated as
PL  α k1−1/α .

(39)This means the behavior of the cache miss ratio obeys
a power law, asymptotically. The same behavior iswell known in computer memory reference, and called
Chow’s empirical power law [16], [17]. On the other
hand, the cache miss ratio for FIFO is given byk,
Nx
where Nx is the number which satisﬁes
PF =4 f (Nx ) − 3 k −

ak

k=m+1

1
.
(k + 1)1/α − k1/α

(40)

9 k2 − 8 k {f (2 Nx ) − f (Nx )} = 0.
(41)

The data used in the trace-driven simulation is access logs of a proxy server at NTT Labs. (at Atsugi,
in March 1997). We focus on the destination IP addresses in the logs and, in this case, the value of α forthe asymptotic power law is 2/3 from graphical observation of Figs. 4(a), (c) and (e).
Figures 7(a) and (b) show the relationship between
cache miss ratio and the capacity of the cache, for LRU
and FIFO, respectively. The horizontal axis denotes
the capacity of the cache and the vertical axis denotes
the cache miss ratio. The black plot denotes the resultsfrom our algorithm and the white plot denotes the results from trace-driven simulations. The solid line denotes theoretical values. These ﬁgures show that ouralgorithm gives a dependable evaluation.
Next, we compare the distributions of the addresses. Figures 8(a) and (b) show the Zipf-type plotsof the destination IP addresses (NTT Labs. at Atsugi,in Nov. 1996) and the pseudo-address sequence obtained from our algorithm, respectively. The horizontal
axes denote the rank order of addresses where all addresses are sorted in descending order according to thefrequencies of appearances. The vertical axes denotethe frequency of the corresponding address appearances(the number of accesses). Figure 8(a) exhibits linearity
in the log-log scale. This is called the Zipf-type distribution and means that only some of the addresses
appear very frequently. On the other hand, Fig. 8 does
not exhibit the concentration of the appearance frequencies. This is because the proposed algorithm isdemocratic for all addresses in the sense that the probability of an address generation is determined only by
the present stack position at the LRU stack. Therefore,
the temporal locality of address appearances strongly
inﬂuence to the cache performances for LRU and FIFO
caches, but the shape of the distribution is not.
8.

Conclusion and Discussion

This paper has shown the structure of the address

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

2149(a) LRU cache.
Fig. 7(b) FIFO cache.

Relations between the cache miss ratio and the capacity of the cache.

(a) the destination IP addresses (NTT labs.
(Atsugi), Nov. 1996).
Fig. 8(b) the address sequence generated from ouralgorithm.

Zipf-type plots of the destination IP addresses.

generation probability from the assumption of timetranslation invariance of ISGF. The structure is an LRU
stack model and has a simple relation between address
generation probability and ISGF. In particular, we haverevealed the following equivalence:
address generation process whose ISGF has atime-translation invariance.

LRU stack model whose probability is (14).
This paper also has shown the general property of
ISGF, that is, the asymptotic power law is applicable
to ISGF in a wide number of Internet access cases. In
addition, by using these results, we have studied properties of the pseudo-address sequence obtained from
our algorithm. This address sequence gives dependable
evaluations of the cache miss ratio.
The proposed algorithm is democratic for all addresses in the sense that the probability of an address
generation is determined only by the present stack position at the LRU stack. In actual Internet usage, someaddresses are accessed with extremely high frequen-cies. This nature is often characterized by Zipf-type
distributions. The address sequence generated fromthe proposed algorithm, however, does not reproduce
these distributions. Let us consider an aging algorithm
which writes the new address over the least frequently
accessed entry. If we choose this aging algorithm fora cache, the address sequence obtained from our algorithm may not give a dependable evaluation. Of course,
because this aging algorithm does not take locality into
consideration, we can choose IRM for an address generation algorithm.
There are probably two reasons why our approachcannot reproduce Zipf-type distributions. Issues weshould study are listed as follows:• Validation of the time-translation invariance of
ISGF.
• Validation of (28) assumed in (29). Equation (28)
is only an asymptotic property.
The time-translation invariance seems to be a natural
assumption. If we denied the assumption, the structure of the address generations loses the Markovian

IEICE TRANS. COMMUN., VOL.E84–B, NO.8 AUGUST 2001

2150

property whose state is described by the generative
LRU stack vector. This may cause a situation wherecomplicated approaches are required. On the other
hand, it is preferable to have the power law adopted
for ISGF replaced by a more strict relationship. However, the behavior of ISGF is probably inessential toreproduce Zipf-type distributions. In order that bothtime-translation invariance and Zipf-type distributions
are compatible, an example of extension for the proposed algorithm has been discussed in [18]. These issues are for further study.

ratio,” IEEE Trans. Comput., vol.38, no.7, pp.1012–1026,
1989.
[18] M. Aida and T. Abe, “Stochastic process of packet destination addresses describing Internet access patterns,” IEICE
Technical Report, IN2000-74 (2000-09), 2000.
[19] M. Aida and T. Abe, “Pseudo-address generation algorithmof packet destinations for Internet performance simulation,”
Proc. IEEE INFOCOM 2001, April 2001.

References[1] C.R. Cunha, A. Bestavros, and M.E. Crovella, “Characteristics of WWW client-based traces,” Tech. Rep. BU-CS-95010, Boston Univ., 1995.
[2] M. Nabe, K. Baba, M. Murata, and H. Miyahara, “Analysis and modeling of WWW traﬃc for designing Internet
access networks,” IEICE Trans., vol.J80-B-I, no.6, pp.428–
437, June 1997.
[3] M. Kobayashi and M.H. MacDougall, “The stack growth
function: Cache line reference models,” IEEE Trans. Comput., vol.38, no.6, pp.798–805, 1989.
[4] R. Jain, “Characteristics of destination address locality incomputer networks: A comparison of caching schemes,”
DEC Tech. Rep., DEC-TR-592, 1990.
[5] S. Glassman, “A caching relay for World Wide Web,” Comput. Networks and ISDN Systems, vol.27, pp.165–173, 1994.
[6] N. Osawa, F. Hayano, T. Yuba, and K. Hakozaki, “Evaluation of replacement policies in WWW cache based on logs
from proxy server,” Tech. Rep. IPSJ, DPS74-33, 1996.
[7] M. Aida, N. Takahashi, and T. Abe, “A proposal of dual
Zipﬁan model describing HTTP access trends and its application to address cache design,” IEICE Trans. Commun.,vol.E81-B, no.7, pp.1475–1485, July 1998.
[8] P.J. Denning and S.C. Schwartz, “Properties of theworking-set model,” Commun. ACM, vol.15, no.3, pp.191–
198, 1972.
[9] J.E. Shemer and G.A. Shippey, “Statistical analysis of
paged and segmented computer systems,” IEEE Trans.
Electronic Computers, vol.EC-15, no.6, pp.855–863, 1966.
[10] R. Turner and B. Strecker, “Use of the LRU stack depth
distribution for simulation of paging behavior,” Commun.
ACM, vol.20, no.11, pp.795–798, 1977.
[11] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker,“Web caching and Zipf-like distributions: Evidence and implications,” Proc. IEEE INFOCOM’99, March 1999.
[12] R. Rousseau and S. Rousseau, “Informetric distributions:
A tutorial review/Les distributions informétriques: Un
aperçu,” Canadian J. Information and Library Science,
vol.18, no.2, pp.51–63, 1993.
[13] M. Aida, N. Takahashi, and M. Matsuda, “Evaluation ofcompulsory miss ratio for address cache and replacement
policies for restoring packet reachability,” IEICE Trans.
Commun., vol.E83-B, no.7, pp.1400–1408, July 2000.
[14] National laboratory for applied network research(NLANR)/Measurement and operations analysis team
(MOAT), http://moat.nlanr.net.
[15] NTT DIRECTORY, http://navi.ocn.ne.jp .
[16] C.K. Chow, “Determination of cache’s capacity and its
matching storage hierarchy,” IEEE Trans. Comput., vol.C25, no.2, pp.157–164, 1976.
[17] D. Thiébaut, “On the fractal dimension of computer programs and its application to the prediction of the cache missMasaki Aida
received his B.Sc. and
M.Sc. degrees in Theoretical Physics from
St. Paul’s University, Tokyo, Japan, in
1987 and 1989, and received the Ph.D.
degree in Telecommunication Engineeringfrom the University of Tokyo, Japan, in
1999. Since he joined NTT Laboratories
in 1989, he had been mainly engaged in research on traﬃc issues in ATM networks
and computer communication networks.
From March 1998 to March 2001, he wasa manager at Traﬃc Research Center, NTT Advanced Technology Corporation (NTT-AT). He is currently a Senior ResearchEngineer at NTT Information Sharing Platform Laboratories.
His current interests include traﬃc issues in communication systems. He received the Young Engineer Award of IEICE in 1996.
Dr. Aida is a member of the IEEE and the Operations ResearchSociety of Japan.

Tetsuya Abe
received his B.Sc.
degree in Physics from Keio University,
Yokohama, Japan, in 1988. He joined
NTT Laboratories in 1988, where hehas been conducting research on processdevice modeling, development on on-chip
RISC controller and designing of highspeed Network-Nodes. Since 2000, he has
been an associate manager at NTT EAST
R&D center. His current interests include
architecture of broadband networks. He
received the Best Industrial ASIC Award of ED&TC in 1996.