Pseudo-Address Generation Algorithm of Packet
Destinations for Internet Performance Simulation
Masaki Aida, Tetsuya Abe
Abstract— 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 thata stochastic process of Internet access satisfies the stationary conditionand 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 tracedriven simulation. The proposed algorithm is applicable not only to thedestination IP address but also to the destination URLs of packets, and isuseful for simulation studies of Internet performance, Web caching, DNS,
and so on.
Keywords—Internet, Destination address, LRU stack, World Wide Web,
Caching.

addresscacheaddress resolution process

packet transfer process

Fig. 1. Packet forwarding in a router.

I. I NTRODUCTIONI

N high-speed data networks, it is necessary to forward packets in a few microseconds or sub-microseconds. Packet forwarding operations include searching for the required address
through an address look-up table. Although the similar searching operations appear also in the designs of DNS and Web content caches, the design of routers in high-speed networks requires the most time-sensitive operations.
To improve and enhance the IP-based Internet-type network, various network architectures, such as IP over ATM [1],NHRP [2], and so on, have been proposed and studied. Packet
forwarding operations at a router consist of the following two
processes.
• address resolution processThis process finds a link address, an ATM address for example, of the destination and/or the next-hop for the destination IP address of the packet.
• packet transfer processThis process transfers the packet by using the link address
obtained from the address resolution process.
Packet processing in the routers within the connection-less network specifically includes the address resolution process. This
process is indispensable for the packet transfer over physicallinks such as ATM, and the efficiency of the address resolution
process has significant influence on the throughput [3]–[5].
Performance of the address resolution process depends on thenumber of arriving packets regardless of their lengths in byte.
On the other hand, performance of the packet transfer processdepends on the amount of bytes to be transferred regardless ofthe number of arriving packets. Performance of packet forwarding operations at a router, therefore, comes from the combined
performance of the two different processes (Fig. 1). In this complicated situation, computer simulations and experimental testM. Aida is with the Traffic Research Center, NTT Advanced Technology Corporation (NTT-AT), Musashino-shi, 180-0006, Japan. E-mail:aida@m.ieice.org .
T. Abe is with NTT East R&D Center. E-mail: tetsuya.abe@rdc.east.ntt.co.jp .

0-7803-7016-3/01/$10.00 ©2001 IEEE

beds probably are powerful approaches to evaluate router performance.
These approaches require a pseudo traffic generator which isbased on a traffic model of Internet access behavior. Interarrival
distribution of the packets and packet length distribution are asignificant part of the traffic model. They have been investigated in [6], [7]. The other significant part of the traffic model isthe assignment of the appropriate destination address to a packet
generated at a pseudo traffic generator. Since address resolution
process includes cache memory look-up of packet address information, performance of this process is strongly influenced fromthe diversity of the destination addresses of the packets.
This paper shows an address generation algorithm which isapplicable to various Internet access patterns, e.g., at access networks, backbone networks, and a WWW server. In addition,
the algorithm can be applicable not only to the destination IP
address but also to the destination URLs of packets. Therefore,
it is expected that the proposed algorithm is useful not only forthe design of routers, but also for the designs of DNS servers,
contents cache servers, and so on.
This paper is organized as follows.
In Sec. II, we introduce the notion of the inverse stack growth
function, used in computer memory reference, for describing thedestination address generations.
In Sec. III, we assume that the inverse stack growth function
has time-translation invariance in order to represent a stationary
generation process of the address, and we derive the result thatthe address generation is described by an LRU stack model. In
addition, we show the relationship between the probability ofaddress generation and the inverse stack growth function.
In Sec. IV, we show address generation algorithm by using the results of Sec. III. As well, we show that the address sequence derived from the proposed algorithm has a timetranslation invariance and reproduces the inverse stack growth
function.
In Sec. V, we investigate the working set size behaviors of actual Internet accesses and show the validation of time-translation

1425

IEEE INFOCOM 2001

invariance and an asymptotic power law of the inverse stackgrowth function. These properties are applicable not only tothe destination IP addresses, but also to the destination URLs, ataccess networks, backbone networks or at a WWW server.
In Sec. VI, we assume the power law of the inverse stackgrowth function, and investigate the property of address sequence generated from the proposed algorithm.
In Sec. VII, we show the effectiveness of the proposed address generation algorithm through performance evaluations of
the address cache.
Section VIII shows conclusions and the residual issues.
II. P RELIMINARY
A. Notations and Definitions
Internet access behaviors include similar issues in computer
memory access patterns. We, therefore, prepare the framework
for Internet access models, using well-known notions in computer memory access models.
Time t is incremented to t + 1 when an access occurs, andt = 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 elementsof W (t, τ ).
• inverse stack growth function (ISGF) [8]: f (t)Expectation value of the number of distinct addresses generated during a period (t, t + τ ],f (t, τ ) := E[w(t, −τ )].

(1)

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

↔

g(t, k) = τ,

or

(2)
(3)

Note that because ISGF f is defined only on integer, SGF gcannot be defined directly. The consistent way to obtain therelation between ISGF and SGF is shown in [8]. Hereafter, we
regard ISGF and SGF as functions defined on the real number
with respect to τ and k, respectively.

information about the next accessed address, IRM cannot
capture locality.
• working set model (WS model) [9]This model assumes that the addresses accessed in thelast W accesses are highly likely to be accessed. The
WS model, therefore, captures locality. The interval W
is called the working set window size. For a given working
set window size W , the smaller working set size w(t, W )means stronger locality.
• least recently used (LRU) stack model [10]An LRU stack is a list of addresses sorted in order according to the times of their most recent access. So, the mostrecently accessed address is at the top of the stack and theleast recently accessed address is at the bottom. The probability that the newly accessed address is the same as theaddress at k-th position in the LRU stack is determined byposition k, and its probability is denoted as ak . Usually, ak
decreases with respect to increases in k. Because the mostrecently accessed address is at the top of the LRU stack,the probability that the next accessed address is the same ishigh. The LRU stack model, therefore, captures locality.
In performance evaluation of address resolutions, the performance of the address cache is an essential object [3], [5]. Cache
performance strongly depends on locality of Internet accesses.
Because IRM cannot take locality into account, it is an insufficient model for Internet access modeling.
Since we can evaluate cache performance if ISGF, f , isgiven [5], ISGF and WS models are important. Hereafter, fromnatural and basic assumptions on ISGF and investigation of theworking set, we show that the address generation probability
must obey an LRU stack model. In addition, we show the relationship between the address generation probability ak and
ISGF f .
III. BASIC S TRUCTURE OF A DDRESS G ENERATIONP ROBABILITY
In this section, we assume that the ISGF f satisfies naturaland basic properties, and investigate the basic structure of an
address generation probability.
A. Assumption
We assume the following property of ISGF.
Time-translation invariance:
ISGF f (t, τ ) is independent of the time t which denotes
time when we start to measure address generation. For anyt, s,f (t, τ ) = f (s, τ ).
(4)

B. Reference Models for Computer Memory
In computer memory references, it is well known that the concept about locality of a reference pattern appears. The locality (especially, temporal locality) implies a high probability ofreuse. A similar concept also appears in Internet access [3].
This subsection reviews typical memory reference models arranged for Internet access models [3].
• independent reference model (IRM)
This model assumes accesses are independent. The probability that a new access has address i is determined by theaddress i (and the probability is denoted as pi ). Accessed
address sequence is generated by i.i.d. and the distribution pi . Because recent accessed addresses do not give any
0-7803-7016-3/01/$10.00 ©2001 IEEE

From this assumption, we denote f (τ ) := f (t, τ ).
Validation of time-translation invariance is discussed in Sec. V
through experimental data.
In queueing models, the typical and usual traffic model as an
input is described by a stationary stochastic process. On theother hand, the notion of a stationary process of address generation is not well-defined yet. However, it is natural to accept that
if the address generation process is stationary, the ISGF shouldhave a time-translation invariance. Thus, the time-translation

1426

IEEE INFOCOM 2001

The size of W is obtained asABC|W ∗ |

Fig. 2. Time intervals A, B and C.

W(A)

W(C)

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

(8)

We can choose m, n and 1 accesses as the periods A, B, and C,
respectively (Fig. 4). Then we have|W ∗ |= {w(t, n + 1) − w(t − 1, n)}− {w(t, n + m + 1) − w(t − 1, n + m)}.
(9)

Applying the time-reversal invariance, we haveW(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)

Fig. 3. Venn’s diagram of working sets.

invariance should be, at least, a necessary condition of the stationarity. We assume it in order to produce a stationary processof the address generation.
Incidentally, we can consider other possibilities for the stationarity condition. For example, we may adopt the assumptionthat the working set size distribution [11],p(k, τ ) := Pr{w(t, τ ) = k},

B. Time-Reversal Invariance
Let us consider f (−τ ). This means the expectation value ofthe number of distinct addresses generated in the period whichis from a time t until the past time t − τ through the backward
derection of time. We have time-reversal invariance for ISGF,
f (t, −τ )f (t − τ − 1, τ )f (τ ).

(6)

We consider three adjacent periods A, B, and C (Fig. 2). Let
the sets of distinct addresses generated in these periods, i.e.,
working set, be W (A), W (B), and W (C), respectively. Figure 3 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 not elements of W (B),i.e., the hatched part in Fig. 3,

0-7803-7016-3/01/$10.00 ©2001 IEEE

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

(12)

Next, we choose n such as f (n) = k − 1 (k = 1, 2, . . .) andchoose m such as f (n + m) = k. Substituting n = g(k − 1)and n + m = g(k), (10) gives
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 most recently accessed address.
Address generation probability:
Here, we define ak as
akC. Address Generation Probability

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

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

(5)

is independent of t. Although this seems to be a stronger stationarity condition than the time-translation invariance of ISGF
f , stationarity of (5) is obtained from (4) as a result. This isbecause the assumption (4) completely determines the fundamental structure of the address generation algorithm, as shownin the following sections.

f (−τ ) ===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 ∗ | isa random variable and can be denoted using indicator function
1{·} by(11)|W ∗ | = 1{X ∈ W (B), X ∈ W (A)}.

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

(14)This means that the probability that X is identical with themost recent 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 kth most recently accessed address is ak . In other words,
address generation must obey the LRU stack model whose
probability is (14).
If {ak ; k = 1, 2, . . .} is the probability, ISGF f must satisfy
ak ≥ 0 and

(7)

1427

∞


ak = 1,(15)

k=1IEEE INFOCOM 2001

B. Time-Translation Invariance and Asymptotic Power Law
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.,

Fig. 4. Time intervals.

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

k→∞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

(16)
bm

=

∞


ak

k=m+1

=

IV. A DDRESS G ENERATION A LGORITHM
This section shows an address generation algorithm by applying the results of the above section. The proposed algorithm
gives a pseudo-address sequence, a sequence of integer.
A. Address Generation Procedure
We define 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 thek-th most recently accessed address as xk . Then
L(i, m) := {x1 , x2 , . . . , xm }.

(k = 1, 2, 3, . . .),Xi = m + 1,

(19)

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

and update L(i + 1, m) and increment i ← i + 1. Returnto 2.
Because the number j can be obtained using a binary searchalgorithm, high-speed address generation is possible.
0-7803-7016-3/01/$10.00 ©2001 IEEEg(k) =

k−1


1
.
b
m=0 m

We define the slope of f as the difference∆f f (g(m) + 1) − f (g(m)):=∆g m(g(m) + 1) − g(m)= bm .

(23)(24)

From (23), we haveg(k) =

k−1

m=0

(18)

by using (14).
3. For the depth m of L(i, m), if m < j, then assign theaddress of new access as(22)

Equation (22) is valid for all m (m = 0, 1, 2, . . .). The probability of a brand-new address generation depends only on thedepth of the generative LRU stack vector. Because the same
depth gives the same probability, bm is independent of thetime when we start to measure address generations. Thus, theaddress sequence obtained from our algorithm reproduces thetime-translation invariance of ISGF.
Let us consider the time that the depth m of the generative
LRU stack vector L(t, m) is incremented to m + 1. Because thetime obeys a geometrical distribution, the mean time is 1/bm.
Therefore, SGF g is obtained as(17)Here, the number of components of L(i, m), m, is called thedepth of L(i, m). Initially, the depth is chosen as 0, i.e., m =0 for L(0, 0). Then m means the number of distinct address
generations.
Let Xi denote the address of the i-th access. Address sequence {Xi ; i = 0, 1, 2, . . .} is generated by the following procedure.
1. Initially, we choose X0 = 1, L(1, 1) = {1} and i = 1.
2. Determine the number j as a realization of the i.i.d. random variable J which obeys the distribution
Pr{J = k} = akf (g(m) + 1) − m.

 −1
∆f 
.
∆g m

(25)

This means the address sequence obtained from the proposed
algorithm reproduces ISGF, f .
V. W ORKING S ET S IZE B EHAVIORS OF I NTERNETACCESSES
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 power law 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 [5], [12]–[14] (strictly, parts of them are Lotoka-type distributions [15]).
Although, in some cases, we can calculate ISGF by using Zipftype distribution [5], [16], it is not always feasible. Therefore, it
is required to determine ISGF from generally applicable property with respect to Internet accesses.

1428

IEEE INFOCOM 2001

Working Set Size, w(t,-τ)Working Set Size, w(t,-τ)

AA
AA
A
AA
A
AA
A
A
AA
AA
AA
A
AAA
AA
A
AA
AAAAAAA
AAA
AA
A
AAAA
AA
AAA
t = 2E+5

1E+3

1E+2

1E+1

t = 4E+5

1E+0
1E+0

1E+1

1E+2

1E+3

1E+4

1E+5

1E+5

1E+4

1E+3

1E+2

1E+1

AAAA
AAA
AAA
AA
AAAA
AA
AAA
AAA
AA
A
AA
A
AA
AAA
AA
A
A
A
AA
AA
A
AA
A
AA
AA
A
A
AA
AA

1E+0
1E+0

1E+6

1E+1

Number of Accesses, τWorking Set Size, w(t,-τ)Working Set Size, w(t,-τ)

t=0

AA
AA
AA
AAAA
AAAAA
AA
AA
AA
A
A
AA
A
A
AA
AAAA
AA
AA
AA
AA
A
A
A
AAA
AA
A
t = 2E+5

1E+2

1E+1

t = 4E+5

1E+0
1E+0

1E+1

1E+2

1E+3

1E+4

1E+3

1E+4

1E+5

1E+6

(b) For the destination URLs
(NTT labs., Mar., 1997).

1E+5

1E+3

1E+2

t = 4E+5

Number of Accesses, τ(a) For the destination IP addresses(NTT labs., Mar., 1997).

1E+4

AA

t = 2E+5

1E+5

1E+6

t=0

AA
AA
AAA
A
A
AAA
AAA
AAA
A
AAA
A
A
AA
AA
AA
AA
AAA
AA
AAAA
AA
AA
A
A
AA
AA
AA
AA
A
A
AA
AAAA
AAAA

1E+5

AAA

t = 2E+5

t = 4E+5

1E+4

1E+3

1E+2

1E+1

1E+0
1E+0

1E+6

Number of Accesses, τ

1E+1

1E+2

1E+3

1E+4

1E+5

1E+6

Number of Accesses, τ(c) For the destination IP addresses(NLANR, Jul. 30, 1999).

(d) For the destination URLs
(NLANR, Jul. 30, 1999).

Fig. 5. Working set size behaviors of destinations (NTT labs. and NLANR).

A. Working Set Size Behaviors and Time-Translation Invarianceof ISGF

working set size can be related to the behavior of ISGF, asw(t, −τ ) ∼ f (t, τ )A.1 Access Logs from Proxy Server of NTT Laboratories
As an example of access networks of the Internet, we investigate access logs of a proxy server at NTT Laboratories. Logs
are for 15 successive days in March 1997.
Figure 5 (a) shows the relationship between working set size,
w(t, −τ ), and the number of accesses, τ , for the destination
IP addresses in log-log scale. Each line indicates w(t, −τ ) fort = 0, 2 × 105 , and 4 × 105 , respectively. Similarly, Fig. 5 (b)shows the relationship between working set size, w(t, −τ ), andthe number of accesses, τ , for the destination URLs in log-log
scale. Each figure shows w(t, −τ ) is independent of t for large
τ . From the law of large number, asymptotic behavior of the
0-7803-7016-3/01/$10.00 ©2001 IEEE(τ  1).

(26)

Thus, these figures imply the time-translation invariance of
ISGF, at least in the asymptotic region, τ  1.
A.2 Access Logs from Cache Server of NLANRAs an example of backbone networks of the Internet, we investigate access logs of a cache server at NLANR [17]. Logs
are for July 30, 1999.
Figure 5 (c) shows the relationship between working set size,
w(t, −τ ), and the number of accesses, τ , for the destination
IP addresses in log-log scale. Each line indicates w(t, −τ ) fort = 0, 2 × 105 , and 4 × 105 , respectively. Similarly, Fig. 5 (d)1429IEEE INFOCOM 2001

Working Set Size, w(t,-τ)

1E+5

1E+4

1E+3

1E+2

1E+1

AA
A
A
A
A
AA
A
AA
AA
AA
A
A
AAAA
AA
AAA
AA
A
AA
AAAA
AA
AA
AA
AA
A
AAA
A

1E+0
1E+0

AA

1E+1

Then, address generation probability (14) is obtained as((k − 1)1/α + 1)α − (k − 1)ak =− (k1/α + 1)α − k .

t = 1.2E+6

t = 2.4E+6

1E+2

1E+3

1E+4

1E+5

1E+6

(29)

Because ak > 0 and
∞


ak

k=1

=

1 − lim

=

1

k→∞



(k1/α + 1)α − k(30)

for 0 < α < 1, {ak ; k = 1, 2, . . .} is probability. The asymptotic behavior of ak is expressed as
1E+7

ak = (1 − α) k −1/α

Number of Accesses, τ(k  1).

(31)

B. Time-Translation Invariance and Asymptotic Power Law
Fig. 6. Working set size behaviors of originations (NTT DIRECTORY, Oct.,1997).

Using power law (28), the probability that the working set
size increases, (22), is expressed asshows the relationship between working set size, w(t, −τ ), andthe number of accesses, τ , for the destination URLs in log-log
scale. These figures also imply the time-translation invarianceof ISGF, at least in the asymptotic region, τ  1.
A.3 Access Logs of NTT DIRECTORY Server

bm

=



(m1/α + 1)α − m .

bm = α m−(1/α−1) + O(m−(2/α−1) ),g(k) =k−1
m=0Therefore,
lim

k→∞

From the above graphical observations, we can recognize thatf (τ ) satisfies a power law with respect to τ for τ  1,

VI. A DDRESS G ENERATION A LGORITHM USING P OWER
L AW
This section investigates pseudo-address generation by applying the power law of ISGF.
A. Address Generation Probability
We assume the asymptotic power law for f (n) is applicablefor all n, i.e.,f (n) = nα .
(28)

(33)


1 1/α−1m+ O(m−1 ) .
α
1log g(k)
= .
log k
α

(34)

(35)

This means the address sequence obtained from our algorithm
reproduces the asymptotic power law of ISGF,
f (n) = nα(27)where α is a constant. A similar property is known in computer
memory access [8]. This property is widely applicable, e.g., foraccess networks, backbone networks, at a WWW server, and forthe destination IP addresses and URLs.

0-7803-7016-3/01/$10.00 ©2001 IEEE

(32)

and (23), we have

B. Asymptotic Power Law(τ  1),

ak

k=m+1

Using the asymptotic behavior of bm ,As an example of WWW servers of the Internet, we investigate access logs of a directory site, NTT DIRECTORY [18].
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 the origination
IP addresses in log-log scale. Each line indicates w(t, −τ ) fort = 0, 1.2 × 106 , and 2.4 × 106 , respectively. This figure also
implies the time-translation invariance of ISGF, at least in theasymptotic region, τ  1.

f (τ )  τ α∞=(n  1).

(36)

VII. C ACHE M ISS R ATIO
A. Theoretical Values for Cache Miss Ratio
In performance evaluation for address resolution, performance of address cache is an essential object. Figure 7 showsan address processing model in a router. The model includes
address cache with k of capacity (k address entries). If the address cache contains the entry corresponding to the destination
address of the packet, the address resolution is immediately carried out. Otherwise, in the case of cache miss, the router must
request an address resolution from a database that has comprehensive information. New address information is written overan entry of the address cache by using aging algorithm.
If we have ISGF f (or SGF g), we can evaluate the cache missratio for the following two classical aging algorithms [5]:1430

IEEE INFOCOM 2001

inquiryaddress cacheaddressDB

overwritekFig. 9. Nx -periods.

.
.
.

A

(aging algorithm:
LRU or FIFO)(1) Address ProcessingBk(2) Towards
an Output PortC

PacketD

Fig. 7. Address processing model in a router.
N_x-period

time I
the next entry
replacedsome entries replaced
k+1
knumber of distinct
addresses

g(k)g(k+1)

number of accesses

Fig. 10. Types of cache entries.

Fig. 8. Interval of entry replacements.

Least Recently Used (LRU)
When cache miss occurs, the new address data is written
over the least recently used entry.
• First In First Out (FIFO)
When cache miss occurs, the new address data is written
over the current oldest entry.
For LRU, the address cache always has k different IP addresses which are the most recently accessed. The number ofaccesses that generate k different IP addresses is g(k). Similarly, the number of accesses that generate k + 1 different IP addresses is g(k + 1). Thus the number of accesses between two
successive replaced entries, is g(k + 1) − g(k) (Fig. 8). Cache
miss ratio, PL , is obtained as
•

PL =

1
.
g(k + 1) − g(k)k{f (2 Nx ) − f (Nx )} .
f (Nx ).

(38)

In addition, the number of IP addresses which have cache entries
at time I and are accessed during the next Nx -period, is equal to
the total number of the cache entries belonging to types B or C
at time I. This is calculated as(k  1).

(39)

1(k + 1)1/α − k 1/αIncidentally, for k  1, (38) is evaluated as
PL = α k 1−1/α

at Nx -period later can be categorized into the following fourtypes (Fig. 10).
A: IP addresses which have corresponding cache entries in
the cache at time I, but are not accessed during the following Nx -period, and their entries expiring at time II.
B: IP addresses which have corresponding cache entries in
the cache at time I, with access during the following Nx period, but their entries expiring at time II.
C: IP addresses which have corresponding cache entries in
the cache at time I, and have cache entries at time II.
D: IP addresses which have no corresponding cache entries
in the cache at time I, but were accessed during the nextNx -period and have cache entries at time II.
The number of IP addresses which are accessed during thelast Nx -period and are not accessed during the next Nx -period
is f (2 Nx) − f (Nx ) (Fig. 11). In case of FIFO, whether a cache
entry survives or not is independent of the frequency of access,and all entries have the same expiration rule. Therefore, thenumber of cache entries of the type A is(37)

Applying the power law (28), we havePL =time II

This means the behavior of the cache miss ratio obeys a powerlaw, asymptotically. The same behavior is well known in computer memory reference, and is called Chow’s empirical powerlaw [19], [20].
For FIFO, unlike LRU, the address cache does not always
have k different IP addresses that are most recently accessed.
Instead, let the expectation value of the number of accesses in
the period, such that all cache entries are replaced, be Nx . In addition, we call the period generating Nx accesses the Nx -period.
Let us consider that the time axis is divided into Nx -periods
as shown in Fig. 9. Then, the cache entries at a certain time and0-7803-7016-3/01/$10.00 ©2001 IEEEk−k {f (2 Nx ) − f (Nx )}.
f (Nx )

Since all cache entries at time II were the missed addresses during the Nx -period from time I to II, the number of cache entries
belonging to type B at time I isf (Nx ) − k.
Therefore, the number of cache entries belonging to type C(same at both time I and II) is1431

2 k − f (Nx ) −k {f (2 Nx ) − f (Nx )}.
f (Nx )IEEE INFOCOM 2001

0.12
our algorithm
0.10
overlapped
accessestheory0.08
0.06

f(2N_x)-f(N_x)

2f(N_x)-f(2N_x)

0.04

Fig. 11. Destination IP addresses generated in adjacent Nx -periods.

0.02
0.00 04 Nxα − 3 k −9 k 2 − 8 k {(2 N

0.10

theory

0.08

0.04

0.00
0

(41)

1000

2000

3000

4000

5000

Capacity of Cache, mFig. 13. Relations between the cache miss ratio and the capacity of the cache(FIFO).

ααx ) − Nx } = 0.

(42)
B. Experimental Results
In order to verify the effectiveness of our algorithm describedin Sec. IV, we compare the cache miss ratios. We show thecache miss ratio which is obtained from simulation with address
sequences generated by our algorithm as input, and compare itwith the results of trace-driven simulation and theoretical values derived from (38) and (41) using (42). The data used in
the trace-driven simulation is access logs of a proxy server at
NTT Laboratories (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 ofFig. 5 (a).
Figures 12 and 13 show the relationship between cache missratio and the capacity of address cache (the number of address
entries), for LRU and FIFO, respectively. The horizontal axis
denotes the capacity of cache and the vertical axis denotes thecache miss ratio. The black plot denotes the results from our algorithm and the white plot denotes the results from trace-driven
simulations. The solid line denotes theoretical values. Thesefigures show that our algorithm gives a dependable evaluation.
0-7803-7016-3/01/$10.00 ©2001 IEEE5000

our algorithm

0.02

Applying the asymptotic power law, (40) is written as

4000

access logs

0.12

Using (40), Nx can be determined. Cache miss ratio for FIFO is
obtained using Nx as
k
PF =
.
Nx

3000

0.14

0.06

9 k 2 − 8 k {f (2 Nx ) − f (Nx )}2000

Fig. 12. Relations between the cache miss ratio and the capacity of the cache(LRU).

= 0.
(40)

4 f (Nx) − 3 k −1000

Capacity of Cache, mCache Miss Ratio, P_F

Let us consider the IP addresses that have cache entries at time
I and are accessed during the next Nx -period, i.e., the cache entries belonging to types B or C. Although they have cache entry
at time I, all the entries do not make hits during the next Nx period. Entries for IP addresses, which fail during the next Nx period are restored as cache entries at time II. Since all entries
expire under the same condition in FIFO, and Nx -period is the
lifetime of a cache entry, the number of restored entries at time
II is half the number of original entries at time I. In other words,
the number of entries belonging to type C at time II is half thatbelonging to types B or C at time I. Therefore, Nx must satisfy
the following condition:

VIII. C ONCLUSION AND D ISCUSSION
This paper has shown the structure of the address generation
probability from the assumption of time-translation invarianceof ISGF. The structure is an LRU stack model and has a simple relation between address generation probability and ISGF.
In particular, we have revealed 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 thesense that the probability of an address generation is determined
only by the present stack position at the LRU stack. In actual Internet usage, some addresses are accessed with extremely high1432

IEEE INFOCOM 2001

frequencies. This nature is often characterized by Zipf-type distributions. The address sequence generated from the 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 for a cache, the address sequence obtained from ouralgorithm 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 approach cannot
reproduce Zipf-type distributions. Issues we should study arelisted 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 property whose state is described by the generative LRU stack vector. This may cause
a situation where complicated approaches are required. On theother 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 to reproduce Zipf-type
distributions. In order that both time-translation invariance andZipf-type distributions are compatible, an example of extension
for the proposed algorithm has been discussed in [21]. Theseissues are for further study.
R EFERENCES
[1]
[2]
[3]

M. Laubach and J. Halpern, “Classical IP and ARP over ATM,” RFC 2225,
1998.
J. V. Luciani, D. Katz, D. Piscitello, B. Cole, and N. Doraswamy, “NBMA
next hop resolution protocol (NHRP),” RFC 2332, 1998.
R. Jain, “Characteristics of destination address locality in computer networks: A comparison of caching schemes,” DEC Tech. Rep., DEC-TR592, 1990.

0-7803-7016-3/01/$10.00 ©2001 IEEE

TMWS99-11, 1999.
M. Aida, N. Takahashi, and T. Abe, “A proposal of dual Zipfian model describing HTTP access trends and its application to address cache design,”
IEICE Trans. Commun., vol. E81-B, no. 7, pp. 1475–1485, 1998.
[6] C.R. Cunha, A. Bestavros, and M.E. Crovella, “Characteristics of WWWclient-based traces,” Tech. Rep. BU-CS-95-010, Boston Univ., 1995.
[7] M. Nabe, K. Baba, M. Murata, and H. Miyahara, “Analysis and modelingof WWW traffic for designing Internet access networks,” IEICE Trans.
Commun., vol. J80-B-I, no. 6, pp. 428–437, 1997.
[8] M. Kobayashi and M.H. MacDougall, “The stack growth function: Cacheline reference models,” IEEE Trans. Comput., vol. 38, no. 6, 1989.
[9] P.J. Denning and S.C. Schwartz, “Properties of the working-set model,”Communications of the ACM, vol. 15, no. 3, 1972.
[10] J.E. Shemer and G.A. Shippey, “Statistical analysis of paged and segmented computer systems,” IEEE Trans. Electronic Computers, vol. EC15, no. 6, 1966.
[11] R. Turner and B. Strecker, “Use of the LRU stack depth distribution forsimulation of paging behavior,” Communications of the ACM, vol. 20,
no. 11, 1977.
[12] S. Glassman, “A caching relay for World Wide Web,” Comput. Networks
and ISDN Systems, vol. 27, pp. 165–173, 1994.
[13] N. Osawa, F. Hayano, T. Yuba, and K. Hakozaki, “Evaluation of replacement policies in WWW cache based on logs from proxy server,”Tech. Rep. of IPSJ, DPS74-33, 1996.
[14] L. Breslau, P. Cao, Li Fan, G. Phillips, and S. Shenker, “Web caching
and Zipf-like distributions: Evidence and implications,” proc. IEEE INFOCOM’99, March 1999.
[15] 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.
[16] M. Aida, N. Takahashi, and M. Matsuda, “Evaluation of compulsory missratio for address cache and replacement policies for restoring packet reachability,” IEICE Trans. Commun., vol. E83-B, no. 7, pp. 1400–1408, 2000.
[17] National laboratory for applied network research (NLANR)/ Measurement
and operations analysis team (MOAT), http://moat.nlanr.net .
[18] NTT DIRECTORY, http://navi.ocn.ne.jp .
[19] C.K. Chow, “Determination of cache’s capacity and its matching storage
hierarchy,” IEEE Trans. Comput., vol. c-25, no. 2, 1976.
[20] D. Thiébaut, “On the fractal dimension of computer programs and its application to the prediction of the cache miss ratio,” IEEE Trans. Comput.,vol. 38, no. 7, 1989.
[21] M. Aida and T. Abe, “Stochastic process of packet destination addresses
describing Internet access patterns,” IEICE Tech. Rep., IN2000-74(200009), 2000.

[5]

1433

IEEE INFOCOM 2001