IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1469

PAPER

Stochastic Model of Internet Access Patterns: Coexistenceof Stationarity and Zipf-Type Distributions
Masaki AIDA† and Tetsuya ABE†† , Regular Members

SUMMARY This paper investigates the stochastic propertyof 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 descriptionsof 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 inﬂuence on the shape ofthe 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.
key words: Internet, destination address, LRU stack, Zipf 'slaw, caching1.

Introduction

To evaluate the performance and quality of service(QoS) of Internet-type networks, it is necessary to understand the stochastic properties of traﬃc characteristics and construct an appropriate model. The important nature of Internet traﬃc patterns is categorizedby two types of characteristics [1], [2]. One concerns
the volume of traﬃc. This includes the interarrival distribution of packets and the packet length distribution.
They have been investigated in [3], [4], and mainly inﬂuence the performance of the queueing mechanisms in
the networks. The other is the destinations of the trafﬁc. This includes the destinations of Internet accesses
as well as packets. They mainly inﬂuence the performance of the caching mechanisms in the networks. This
paper focuses on the latter issues.
The fact that computer memory references exhibit
locality behavior is now well established [5]. Raj Jain
reported that frames on computer networks also exhibit locality behavior in the destinations of packets[1]. Since the cache performance is inﬂuenced by locality behavior, it is important for evaluating Internet
performance. In general, comparisons of the performances of diﬀerent caching mechanisms are conducted
Manuscript received June 15, 2001.
Manuscript revised February 26, 2002.
†
The author is with NTT Information Sharing Platform
Laboratories, NTT Corporation, Musashino-shi, 180-8585
Japan.
††
The author is with NTT EAST R&D Center, Tokyo,163-8019 Japan.

through trace-driven simulations [1], [6], [7]. These use
logs of actual Internet accesses as input traﬃc for thesimulation. Hence, we can reproduce a speciﬁc network traﬃc situation by using trace-driven simulation,
but cannot obtain information about other types of networks. Aida and Abe [8], [9] investigated the stochastic
properties of Internet access patterns and showed thestochastic process that describes Internet access destinations by assuming the process is stationary. Moreprecisely, if we assume a stationary condition for the address generation process, the process is a least recently
used (LRU) stack model. Simultaneously, this model
can describe locality behavior (especially, temporal locality) in Internet access patterns. Many experimental
data support the stationary condition of the process
and the process accurately gives cache performance forvarious Internet access patterns.
On the other hand, it is well known that Internet
access destinations exhibit concentrated distributions[2], [7], [10]. For example, only some of the destinations
appear very frequently. Such distributions are characterized by Zipf-type distributions and appear frequently
in various Internet access patterns.
Unfortunately, the LRU stack model shown in [8],[9] does not reproduce Zipf-type distributions. In otherwords, the stationary condition and the Zipf-type distributions are not compatible in the present model.
If our purpose is only reproduction of Zipf-type
distributions, we can take the independent reference
model, which is a simple and primitive model for Internet access patterns. This model assumes accesses are
independent. The probability that a new access has address i is determined by address i and the probability
is denoted as pi . Accessed address sequence is generated by i.i.d. and the distribution pi . Because recently
accessed address do not give any information about thenext address, the independent reference model cannot
capture temporal locality [1]. So, the model cannot give
appropriate cache performance. Although this model
may reproduce Zipf-type distributions by using Zipftype distribution pi , it is insuﬃcient model that describes Internet access patterns.
This paper investigates the stochastic property of
packet destinations in order to allow the coexistenceof the stationary condition and Zipf-type distributions.
Although the pseudo-address sequences generated fromthe LRU stack model do not reproduce Zipf-type dis-

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1470

• Inverse Stack Growth Function (ISGF) [5]: f (t, τ )The expectation value of the number of distinct
addresses generated during a period (t, t + τ ],tributions, we can recognize that the LRU stack model
gives appropriate descriptions of address generation on
the medium/long time-scale. This property implies
that the address generation behavior on the short timescale has a strong inﬂuence on the shape of the distributions that describe the 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/longtime-scale, and shows that the proposed algorithm reproduces the Zipf-type distributions.
This paper is organized as follows.
In Sect. 2, we introduce the notions of the workingset size, the inverse stack growth function (ISGF), andthe LRU stack model, used in computer memory reference, in order to describe the destination address generations.
In Sect. 3, we investigate Internet accesses patterns
with respect to both working-set size behaviors andthe distributions of packet destination addresses. Thissection shows that actual Internet access patterns arecharacterized by the behavior of ISGF and Zipf-type
distributions.
In Sect. 4, we assume that the ISGF is stationary, and investigate the characteristics of the pseudoaddress sequence obtained from the stationary address
generation process described by an LRU stack model.
This section shows that the stationary address generation process cannot reproduce Zipf-type distributions.
In Sect. 5, we introduce a weak stationary condition into the ISGF, and propose a new address generation process that meets the stationary condition on themedium/long time-scale.
In Sect. 6, we show that the proposed address generation process shown in Sect. 5 reproduces the characteristics of actual Internet access patterns described in
Sect. 3: both the working-set behaviors and Zipf-type
distributions appear in actual Internet access patterns.
2.

f (t, τ ) := E[w(t, −τ )].

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 = f −1 .

↔

g(t, k) = τ,

or

(3)
(4)

Note that because ISGF f is deﬁned only for integers, SGF g cannot be deﬁned directly. The consistent way to obtain the relationship between ISGF
and SGF is shown in [5]. Hereafter, we regard
ISGF and SGF as functions deﬁned for real numbers with respect to τ and k, respectively.
• Least Recently Used (LRU) stack model [11]In computer memory references, it is well known
that the concept about the locality of a reference
pattern appears. The locality (especially, temporal
locality) implies a high probability of reuse. The
LRU stack model is one computer memory reference model that can describe temporal locality.
An LRU stack is a list of addresses sorted in orderaccording to the times of their most recent access.
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 thek-th position in the LRU stack is determined byposition k, and its probability is denoted as ak .
Usually, ak decreases as k increases. Because themost recently accessed address is at the top of the
LRU stack, there is a high probability that the next
address to be accessed will be the same.
3.

Notation and Deﬁnitions(2)

Characteristics of Internet Access Patterns

Internet access behaviors involve similar issues to computer memory reference patterns. We, therefore, basethe framework for Internet access models, on wellknown notions in computer memory access models.
Time t is incremented to t + 1 when an access occurs, and t = 0, ±1, ±2, . . ..

This section gives a brief review of the characteristics ofInternet access patterns: the working-set behavior anddestination address distributions. We investigated access logs of a proxy server at NTT Laboratories. They
covered 15 successive days in March 1997 when there
were 351,968 accesses.

• Working Set: W (t, τ )The set whose elements are distinct addresses generated during a period [t − τ, t) (i.e., {t − τ, t − τ +1, . . . , t − 1}). 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, τ ),3.1 Working Set Size Behaviors and Time-Translation
Invariance of ISGF

w(t, τ ) := |W (t, τ )|.

(1)

The characteristics of the working-set size behaviors forInternet access patterns have been investigated in [8],[9].
Figure 1 shows the relationship between working
set size, w(t, −τ ), and the number of accesses, τ , forthe destination IP addresses on a log-log scale. LinesAIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

1471

Fig. 1 Working set size behaviors of destination IP addresses(NTT Labs., March 1997).

Fig. 2

Lotoka-type plot of the destination IP addresses.

Fig. 3Zipf-type plot of the destination IP addresses.

indicate w(t, −τ ) for t = 0, 2 × 105 , and 4 × 105 , respectively.
This ﬁgure reveals two characteristics:• w(t, −τ ) is independent of t for large τ .
• w(t, −τ ) exhibits a power law behavior with respect to τ for large τ .
From the law of large numbers, asymptotic behavior of
the working set size can be related to the behavior of
ISGF, asw(t, −τ ) ∼ f (t, τ )

(τ

1),

(5)

where F (x) ∼ G(x) means limx→∞ F (x)/G(x) =1. Thus, the ﬁrst characteristic implies the timetranslation invariance of ISGF, for any t and s,f (t, τ ) = f (s, τ )

(τ

1),

(6)

at least in the asymptotic region, τ
1. Similarly,
the second characteristic implies that f (t, τ ) satisﬁes apower law with respect to τ for τ1,
f (t, τ )

τα

(τ

1),

(7)

where α is a constant. A power law behavior of ISGF
is known in computer memory access [5].
These properties are widely applicable, e.g., for access networks, backbone networks, at a WWW server,
and for the destination IP addresses and URLs [8], [9].
3.2 Destination Address Distributions
It is well known that the destination addresses or URLs
are characterized by Zipf-type distributions [2], [3], [6],[7], [10]. (strictly, some of them are Lotoka-type distributions [12]).
Figures 2 and 3 show Zipf-type plots of the destination IP addresses.

In Fig. 2, the horizontal axis denotes the frequency
n of appearances (the number of accesses). The verticalaxis denotes the number of addresses that appeared ntimes. This ﬁgure exhibits linearity on the log-log scale
for small n. This is called Lotoka’s law or Zipf’s 2nd law
and means that many addresses have a low frequency
of appearances.
In Fig. 3, the horizontal axis denotes the rank order m of addresses where all addresses are sorted in descending order according to the frequencies of appearances. The vertical axis denotes the frequency of thecorresponding address appearances (the number of accesses). This ﬁgure also exhibits linearity on the log-log
scale for small m. This is called Zipf’s law and meansthat only some of the addresses appear very frequently.
In this paper, both Lotoka’s and Zipf’s laws arecalled Zipf-type distributions.

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1472

accessed address as xk . Then
4.

Address Generation Process and Stationarity

In this section, we show the stationary process ofaddress generation whose ISGF f satisﬁes the timetranslation invariance, and investigate the characteristics of the generated pseudo-address sequence.
4.1 Assumption
From the discussion in Sect. 3 based on experimental
data, it is natural to assume the following property of
ISGF for all τ .
Time-translation invariance:
ISGF f (t, τ ) is independent of the time t that denotes the time when we start to measure address
generation. For any t, s,f (t, τ ) = f (s, τ ).

(8)

From this assumption, we denote f (τ ) := f (t, τ )and g(k) := g(t, k) .
We assume this in order to produce a stationary processof address generation. Although (6) has the restrictionon τ , (8) is assumed for all τ .

(10)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 that obeys the distribution
Pr{J = k} = ak(k = 1, 2, 3, . . .),(11)

by using (9).
3. For the depth m of L(i, m), if m < j, then assign
the address of new access as
Xi = m + 1,

(12)

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 the new access as
X i = xj ,4.2 Stationary Address Generation Process(13)

and update L(i + 1, m) and increment i ← i + 1.
Return to 2.

First, we introduce the probability ak as
ak := {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k} .

L(i, m) := {x1 , x2 , . . . , xm }.

(9)

Our previous studies [8], [9] showed that the address
generation process is described by the LRU stack modelthat has probability ak for selecting the k-th positionon the LRU stack, if and only if the ISGF is timetranslation invariant (8). This means that the probability that a newly accessed address X is identical withthe most recently accessed address is a1 , the probability
that X is identical with the 2nd most recently accessed
address is a2 , . . ., and the probability that X is identical with the k-th most recently accessed address is ak .
The derivation of (9) is described in Appendix A.
4.3 Address Generation Algorithm
This subsection shows an address generation algorithm
based on the LRU stack model mentioned above. Thisalgorithm gives a pseudo-address sequence, a sequenceof integers [8], [9].
We deﬁne the generative LRU stack vector L(i, m)
as follows. At the time immediately before the i-th
(i = 0, 1, 2, . . .) address generation, we denote the mostrecently accessed address as x1 , the 2nd most recently
accessed address as x2 , . . ., and the k-th most recently

Because the number j can be obtained using a binary
search algorithm, high-speed address generation is possible (see Appendix B).
4.4 Destination Address Distributions
This subsection shows the distributions of the pseudoaddress sequence obtained from the above mentioned
LRU stack model that satisﬁes the time-translation invariance of ISGF (8). We use the speciﬁc expression of
ISGF asf (τ ) = τ α ,(14)

for all τ and set α = 2/3 from graphical observationof Fig. 1. Then, the form of the probability (9) is expressed as
ak = ((k − 1)1/α + 1)α − (k − 1)(15)
− (k1/α + 1)α − k .
Figures 4 and 5 show Lotoka-type and Zipf-type plots
for the pseudo-address sequence, respectively. The
length of the pseudo-address sequence is 350,000. They
are drawn to the same scale as Figs. 2 and 3 for ease ofcomparison.

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

1473

the address generations loses the Markovian property
whose state is described by the generative LRU stackvector. This may cause a situation where complicatedapproaches are required. In particular, Fig. 1 gives thevalidation of (6) which is the time-translation invariance of ISGF at least in the asymptotic region τ
1.
On the other hand, it is preferable to have the powerlaw adopted for ISGF replaced by a stricter relationship. However, the behavior of ISGF is probably notessential to reproduce Zipf-type distributions.
Hereafter, we introduce violations of (8) and (14)into our model, and try to support the coexistence ofstationarity and Zipf-type distributions.
5.
Fig. 4 Lotoka-type plot of the pseudo-address sequencesatisfying the time-translation invariance (8).

Address Generation Process with Asymptotic Time-Translation Invariance

5.1 Approach
Let us consider the partial violation of the timetranslation invariance (8) for small τ . Figure 1 does
not validate (8) for small τ . So we use the asymptotic
time-translation invariance (6), and try to modify theaddress generation process in order to reproduce a Zipftype distribution.
The strict time-translation invariance is valid if
and only if the generation process is the LRU stackmodel with probability (9). Therefore, if we use anything except the LRU stack model, the time-translation
invariance (8) is naturally violated. This means that wehave many possibilities for constructing the extended
address generation process. Hereafter, we impose thefollowing three requirements, and introduce the violation of the time-translation invariance into our address
generation model.

Fig. 5 Zipf-type plot of the pseudo-address sequence satisfying
the time-translation invariance (8).

Unlike Figs. 2 and 3, Figs. 4 and 5 do not exhibit
the concentration of appearance frequencies. This isbecause the LRU stack model 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. Therefore, the shape of the Zipftype distributions are not reproduced from the LRU
stack model.
There are probably two reasons why the LRU stackmodel mentioned above cannot reproduce Zipf-type distributions. They are related to:• Assuming the time-translation invariance (8) of
ISGF.
• Assuming (14) in (15).
Equations (8) and (14) are only asymptotic properties.
The time-translation invariance seems to be a natural
assumption. Without this assumption, the structure of• On the medium/long time-scale, the model behaves the same as the LRU stack model describedin Sect. 4.2.
• On the short time-scale, the model has diﬀerent behavior from the LRU stack model, but its structure
can be adjusted to the LRU stack model describedin Sect. 4.2.
• Only some of the addresses appear very frequently.
We take these three requirements into consideration and construct the extended model.
First, the probability (9) that the k-th stack position is selected is rewritten as
ak = {f (n(k)) − f (n(k) − 1)}− {f (n(k + 1)) − f (n(k + 1) − 1)} ,(16)

where n(k) denotes that there have been n(k) accesses
since the time when the address at the k-th position of
the LRU stack most recently appeared, and n(1) = 1.
Because, for k1,n(k)g(k − 1) + 1

(k

1),

(17)

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1474

Relationship between n(k) and g(k − 1).

Fig. 6(16) is equivalent to (9) for k
1 (see Fig. 6), and the
LRU stack models using (16) and (9) show the same
behavior for k
1. The expression of the probability(16) in k
1 is for an easy connection to the probability on a short time-scale, as shown below.
Next, we introduce a threshold parameter κ to separate the time scale into short and medium/long. If
the stack position k selected by the probability (16) isk > κ, the address generation obeys the ordinary LRU
stack model. If k ≤ κ, let us consider the probabilityan , which denotes the probability that a new access has
the same address as appeared n access ago. By natural
rewriting of (16), we assumean = {f (n) − f (n − 1)}− {f (n + 1) − f (n)} .

Fig. 7 Relationship between the complete list of all generated
addresses and the LRU stack.

(18)

The relationship between (16) and (18) can be written
as follows. For k ≤ κ,n(k+1)−1

ak =


an .

(19)

n=n(k)

Fig. 8

Example of address generation for the proposed model.

For example,
a1 = 
a1 + 
a2 + · · · + an(2)−1 ,an(2) + an(2)+1 + · · · + an(3)−1 ,a2 = 

(20) and (21) are
(20)
(21)

and so on. The subscript k of ak denotes a stack position of the LRU stack, but the subscript n of an denotes
the number of accesses that shows a new access has thesame address as appeared n access ago. Since probability (18) is not in the form of (9), the address generation
process by (18) is not an LRU stack model and it is nottime translation invariant. From another viewpoint,(18) is the probability of selecting the n-th stack position in an LRU stack, if all generated addresses aremutually diﬀerent and thus the LRU stack has the complete list of all generated addresses. Figure 7 shows therelationship between the complete list of all generated
addresses and the LRU stack. The complete list includes the same address but the LRU stack does not.
Figure 8 shows an example of the generated address according to (16) or (18). For k ≤ κ, i.e., n ≤ n(κ+1)−1,a1 = 
a1 + 
a2 ,
a2 = 
a3 + 
a4 + 
a5 + 
a6 ,

(22)
(23)

in an example of Fig. 8. On the short time-scale, multiple appearances of the addresses cause strong autocorrelation. This structure allows frequently accessed
addresses to have an extremely high frequency.
5.2 Separation of Time Scale
This section shows a way to determine the valueof κ, which separates the time scale into short andmedium/long. To examine ISGF behaviors in detail,we utilize the cache performance for the LRU cache.
This is because the cache miss ratio for the LRU cache
is closely related to the ISGF behavior.
As shown in [2], [8], the theoretical value of cache
miss ratio for LRU is obtained through the following

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

1475

formula. For LRU cache, the cache miss ratio, PL , isgiven byPL =1,g(k + 1) − g(k)(24)

where k denotes the capacity of the cache (the numberof address entries). Therefore, ISGF (or SGF) completely determines the cache miss ratio. Applying thepower law (14), we havePL =1(k + 1)1/α − k1/α

.

(25)

We show the cache miss ratio obtained from simulation with the pseudo-address sequence generated by
the stationary address generation algorithm as input,
and compare it with the results of trace-driven simulation and theoretical values. The pseudo-address sequence and the theoretical value are obtained by using
the power law (14) with α = 2/3 from graphical observation of Fig. 1. The data used in the trace-driven
simulation was the same access logs as used in Sect. 3.
Figure 9 shows the relationship between cache missratio and the LRU cache capacity. The horizontal axis
denotes the cache capacity and the vertical axis denotes the cache miss ratio. The black plots denote results from trace-driven simulation and the white ones
denote results from the LRU stack model. The solidline denotes theoretical values. This ﬁgure shows thatthe stationary address generation algorithm gives a dependable evaluation in particular for large cache capacity k
1. This means that the asymptotic timetranslation invariance (6) is re-validated. On the other
hand, for k 1, there is a diﬀerence between the values obtained from the trace-driven simulation and thoseobtained from the pseudo-address sequence. This difference implies the violation of the time-translation invariance of ISGF on the short time-scale. The value ofκ ranges from about 1000 to a few hundred.

5.3 Proposed Address Generation Algorithm
This subsection shows an extension of the stationary
address generation algorithm. The extension is carried out according to the three requirements shown in
Sect. 5.1.
We deﬁne the generative LRU stack vector L(i, m)
as follows. At the time immediately before the i-th
(i = 0, 1, 2, . . .) address generation, we denote the mostrecently 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 }.

(26)

In addition, we deﬁne another vector N(i, m), whosek-th component denotes that there have been n(k) accesses since the time when the address at the k-th component of the generative LRU stack vector L(i, m) waslast accessed.
N(i, m) := {n(1), n(2), . . . , n(m)}(27)

Here, the number of components of L(i, m) andN(i, m), m, is called the depth of L(i, m) and N(i, m).
Initially, the depth is chosen as 0, i.e., m = 0 for L(0, 0)
and N(0, 0). Then m means the number of distinct address generations.
Let Xi denote the address of the i-th access. We
deﬁne the generative address vector X(i) as follows. At
the time immediately before the i-th (i = 0, 1, 2, . . .)address generation, X(i) has the generated addresses
in the past as its components,
X(i) := {X0 , X1 , . . . , Xi−1 }.

(28)

Address sequence {Xi ; i = 0, 1, 2, . . .} is generated by
the following 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 that obeys the distribution
Pr{J = k} = ak(k = 1, 2, 3, . . .),(29)

by using (16).
3. For the depth m of L(i, m), if m < j, then assign
the address of the new access as
Xi = m + 1,

(30)

and update both L(i+1, m+1) and N(i+1, m+1),
and increment i ← i + 1. Return to 2.
4. For the depth m of L(i, m), if m ≥ j and j > κ,then assign the address of the new access as
X i = xj ,Fig. 9 Relationships between the cache miss ratio and the LRU
cache capacity.

(31)

and update both L(i+1, m+1) and N(i+1, m+1),
and increment i ← i + 1. Return to 2.

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 20021476

5. For the depth m of L(i, m), if m ≥ j and j ≤ κ,
then determine the number l as a realization of thei.i.d. random variable L that obeys the distribution
Pr{L = n} = an(n = 1, 2, 3, . . .),(32)

by using (18). Next, assign the address of the newaccess as
Xi = Xi−l ,(33)(where Xi−l is a component of X(i)) and update
both L(i + 1, m + 1) and N(i + 1, m + 1), and increment i ← i + 1. Return to 2.
Because the numbers j and l can be obtained using abinary search algorithm, high-speed address generationis possible.
6.

Figures 11 and 12 show Lotoka-type and Zipf-type
plots, respectively, for the pseudo-address sequence obtained from the proposed algorithm. The length of thepseudo-address sequence is 350,000. They are drawn to
the same scale as Figs. 2 and 3 for ease of comparison.
Like Figs. 2 and 3, Figs. 11 and 12 exhibit a concentration of the appearance frequencies and reproduce theZipf-type distributions.
7.

Conclusions

In this paper, we have investigated an address generation process that can reproduce Zipf-type distributions.
Both stationarity and Zipf-type distributions frequently appear in Internet access patterns. If we assume the stationary condition as the time-translation
invariance of ISGF, the address generation process

Experimental Results

First, we investigate the working-set size behaviors of
the pseudo-address sequence obtained from the generation algorithm described in Sect. 5.3. Here, f in (16)and (18) is assumed to be the power law (14) withthe parameter α = 2/3. In addition, from the resultof Sect. 5.2, we set the threshold parameter κ = 1000.
Figure 10 shows the relationship between working set
size, w(t, −τ ), and the number of accesses, τ , for thedestination IP addresses on a log-log scale. Lines indicate w(t, −τ ) for t = 4 × 106 , 8 × 106 , and 1.2 × 107 ,respectively.
This ﬁgure has the same characteristics as Fig. 1.
From the law of large numbers (5), the asymptotic behavior of the ISGF has the properties of• Time-translation invariance and• Power law behavior.

Fig. 10 Working-set behaviors of the pseudo-address sequenceobtained from the proposed algorithm.

Fig. 11 Lotoka-type plot of the pseudo-address sequenceobtained from the proposed algorithm.

Fig. 12 Zipf-type plot of the pseudo-address sequence obtained
from the proposed algorithm.

AIDA and ABE: STOCHASTIC MODEL OF INTERNET ACCESS PATTERNS

1477

cannot reproduce Zipf-type distributions. From thecache performance, the time-translation invariance on
the medium/long time-scale is a reasonable assumption. So, we introduce two structures into our model:
one is violation of the invariance relationship on the
short time-scale and the other is its restoration on themedium/long time-scale. Based on these structures, we
propose a new address generation algorithm.
The time-translation invariance of the proposed algorithm is restored on the medium/long time-scale, andZipf-type distributions appear. Since the way of violating the time-translation invariance is not unique, theproposed algorithm is one of several possibilities. However, we note the following two signiﬁcant points.
• Symmetry breaking on a short time-scale strongly
aﬀects the distribution of the long-time sequence.
• Zipf-type distributions are compatible with stationality on the medium/long time-scale.
References[1] R. Jain, “Characteristics of destination address locality incomputer networks: A comparison of caching schemes,”
DEC Tech. Rep., DEC-TR-592, 1990.
[2] 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.
[3] C.R. Cunha, A. Bestavros, and M.E. Crovella, “Characteristics of WWW client-based traces,” Tech. Rep. BU-CS-95010, Boston Univ., 1995.
[4] M. Nabe, K. Baba, M. Murata, and H. Miyahara, “Analysis and modeling of WWW traﬃc for designing Internet
access networks,” IEICE Trans. Commun. (Japanese Edition), vol.J80-B-I, no.6, pp.428–437, June 1997.
[5] 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.
[6] S. Glassman, “A caching relay for World Wide Web,” Comput. Networks and ISDN Systems, vol.27, pp.165–173, 1994.
[7] 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.
[8] M. Aida and T. Abe, “Pseudo-address generation algorithmof packet destinations for Internet performance simulation,”
Proc. IEEE INFOCOM 2001, pp.1425–1433, April 2001.
[9] M. Aida and T. Abe, “Stochastic model of Internet access patterns,” IEICE Trans. Commun., vol.E84-B, no.8,
pp.2142–2150, Aug. 2001.
[10] L. Breslau, P. Cao, Li Fan, G. Phillips, and S. Shenker,“Web caching and Zipf-like distributions: Evidence and implications,” Proc. IEEE INFOCOM’99, pp.126–134, March
1999.
[11] J.E. Shemer and G.A. Shippey, “Statistical analysis of
paged and segmented computersystems,” IEEE Trans.
Electron. Comput., vol.EC-15, no.6, pp.855–863, 1966.
[12] R. Rousseau and S. Rousseau, “Informetric distributions:
A tutorial review/Les distributions informétriques: Un
aperçu,” Canadian Journal of Information and Library Science, vol.18, no.2, pp.51–63, 1993.

Appendix A:

Address Generation Probability

We consider three adjacent periods A, B, and C(Fig. A· 1). Let the sets of distinct addresses generated
in these periods, i.e., working set, be W (A), W (B),and W (C), respectively. Figure A· 2 denotes Venn’s
diagram of 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. A· 2,
W ∗ := {W (A) ∩ W (C)} \ W (B).

(A· 1)The size of W ∗ is obtained as|W ∗ | = |{W (A) ∩ W (C)} \ W (B)|
= {|W (B) ∪ W (C)| − |W (B)|}− {|W (A) ∪ W (B) ∪ W (C)|− |W (A) ∪ W (B)|} .

(A· 2)

We can choose m, n and 1 accesses as the periods A,
B, and C, respectively (Fig. A· 3). Then we have|W ∗ | = {w(t, n + 1) − w(t − 1, n)}− {w(t, n + m + 1) − w(t − 1, n + m)}.
(A· 3)
Applying the time-translation invariance (8), we have
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)}. (A· 4)
The physical meanings of E [|W ∗ |] are as follows. |W ∗ |Fig. A· 1

Fig. A· 2

Time intervals A, B and C.

Venn’s diagram of working sets.

Fig. A· 3

Time intervals.

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1478

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)}.

(A· 5)

Therefore, E [|W ∗ |] means the probability of |W ∗ | = 1(the expectation of an indicator function is a probability),
E [|W ∗ |] = Pr{X ∈ W (B), X ∈ W (A)}.

Address generation probability:
Here, we deﬁne ak as(A· 8)

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 (A· 8).
Appendix B:

Masaki 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 joining NTT Laboratories in
1989, he has been mainly engaged in research on traﬃc issues in ATM networks
and computer communication networks.
From March 1998 to March 2001, he was amanager at Traﬃc Research Center, NTT Advanced Technology
Corporation (NTT-AT). He is currently a Senior Research Engineer in NTT Information Sharing Platform Laboratories. His
current interests include traﬃc issues in communication systems.
He received the Young Investigators Award of IEICE in 1996.
Dr. Aida is a member of the IEEE and the Operations ResearchSociety of Japan.

Determination of the Number jThis section shows a way to determine the number j asa realization of the i.i.d. random variable J that obeys
the distribution
Pr{J = k} = {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k}(k = 1, 2, 3, . . .).

(A· 9)

Because f (g(k) + 1) − k decreases with respect tok andf (g(0) + 1) − 0 = 1,
lim f (g(k) + 1) − k = 0,k→∞then we can determine j = k (see Fig. A· 4). Thus, we
can determine the number j by using a binary searchalgorithm comparing ξ with f (g(k) + 1) − k for appropriate ks.

(A· 7)

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

ak := {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k} .

Searching for the number k satisﬁes (A· 12).

(A· 6)

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), (A· 4) gives
E [|W ∗ |] = {f (g(k − 1) + 1) − (k − 1)}− {f (g(k) + 1) − k} .

Fig. A· 4(A· 10)(A· 11)the following simple procedure is applicable. Let ξ bea realization of the i.i.d. random variable that is uniformly distributed on [0,1]. If a number k satisﬁes
f (g(k)+1)−k < ξ ≤ f (g(k−1)+1)−(k−1), (A· 12)

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 and development on onchip RISC controller and designing of
high-speed network-nodes. Since 2000, he
has been an associate manager at NTT
EAST R&D Center. His current interests include security of services on broadband networks. He received the Best Industrial ASIC Award of
ED&TC in 1996.