IEICE TRANS. COMMUN., VOL.E83–B, NO.7 JULY 2000

1400

PAPER

Evaluation of Compulsory Miss Ratio for Address Cacheand Replacement Policies for Restoring Packet
Reachability
Masaki AIDA† , Regular Member, Noriyuki TAKAHASHI†† , Nonmember,and Michiyo MATSUDA† , Regular Member

SUMMARY In high-speed data networks, it is important toexecute high-speed address resolution for packets at a router. To
accomplish high-speed address resolution, address cache is eﬀective. For HTTP accesses, it has been discussed that the Dual
Zipﬁan Model can describe the distribution of the destination IP
addresses, and it enabled us to derive the cache miss ratio in
the steady state, i.e., the cache miss ratio when the cache has
full entries. However, at the time that systems are initialized or
network topology is changed, the address cache has no address
information or invalid address information. This paper shows
the compulsory miss ratio which is the cache miss ratio when
the cache has no address entry. In addition, we discuss the replacement policies of cache entries, for fast recovery of packet
reachability, when the cache has information of unreachable address.
key words: HTTP, cache, dual Zip an model, compulsory miss,

purge

1.

Introduction

To improve and enhance the IP-based Internet-type
network, various network architectures has been proposed and studied, such as IP over ATM [1], NHRP
[2], and so on. For the purpose of bringing a highspeed, a rich bandwidth, and a wider area-cover to theconnection-less network like the Internet, minimizing adelay in the packet processing has a much importance.
Packet processing in the routers within theconnection-less network speciﬁcally includes the address resolution process, through which the router ﬁnds
a link address, an ATM address for example, of thedestination and/or the next-hop for the destination IP
address of the packet. This process is indispensable forthe packet transfer over physical links such as ATM,and eﬃciency of the address resolution process has signiﬁcant inﬂuence to the throughput [3]–[5].
To speed up address resolution, edge routers whichaccommodates users are usually equipped with cachetables for the addresses. When the router has the cache
entry for the destination of the packet (as the result
Manuscript received May 20, 1999.
Manuscript revised November 29, 1999.
†
The authors are with Traﬃc Research Center, NTT
Advanced Technology Corporation (NTT-AT), Musashinoshi, 180-0006 Japan.
††
The author is with NTT Network Innovation Laboratories, Yokosuka-shi, 239-0847 Japan.

of processing the earlier packet to the same destination), address resolution is immediately carried out.
Otherwise, the router must utilize more exhaustive
but timely-expensive method to resolve the address,
such as requesting resolution to the address server [1](Fig. 1(a)) and waiting for the response, or sending thepacket to the default router [2] (Fig. 1(b)). Thougheither the address server or the default router has comprehensive address information, they can be a performance bottleneck if the frequency of cache miss in the
network goes beyond their capacities. Therefore estimation of the cache miss ratio (or conversely the cache
hit ratio) is important and desired as it has impact on
the required performance of the address server or thedefault server, the network performance, and the designof the network.
The cache miss ratio is categorized according tosituations as follows:• Capacity miss ratio
This is the cache miss ratio in the steady state,i.e., the cache miss ratio when the cache has full
entries.
• Compulsory miss ratio
This is the transitional behavior of the cache missratio when the cache is not full.
[4] discussed that the Dual Zipﬁan Model can describe the distribution of the destination IP addressesof HTTP traﬃc, and drive the capacity miss ratios inthe steady state. Although system works in the steadystate in usual, there are some exceptions. For example,• At the initialization of a system:
Re-initialization of a system is required when thesystem is in trouble. That time, all information in
address cache will be lost.
• After purge operation of the address cache:
When troubles on a transmission link occur or network topology changes, address information in theaddress cache can not guarantee packet reachability. In order to restore packet reachability, renewalof cache entries is required. A purge operation,
which deletes all the cache entries, is used to restore packet reachability. After a purge operation,
the address cache has no address information.

AIDA et al.: EVALUATION OF COMPULSORY MISS RATIO FOR ADDRESS CACHE

1401

2.

Background

2.1 Dual Zipﬁan Model(a) Address resolution using an address server.

(b) Address resolution using the default router.
Fig. 1

Network models.

When the cache entries are lost after re-initialization
or a purge, the cache miss ratio jumps high. After
that, the cache miss ratio descends gradually and approaches the capacity miss ratio in the steady state.
These transitional behaviors of the cache miss ratio are
the compulsory miss ratio.
When the cache entries are lost and the cache missratio jumps high, it brings a serious deterioration of
network performance. In case of Fig. 1(a), the routermust request address resolution from the address server
frequently, and the load of the address server greatly increases. In case of Fig. 1(b), the router sends the packet
to its default router frequently, and the load of the default router greatly increases. These heavy loads arecaused by the high compulsory miss ratio. In order todesign actual networks and estimate their performance,
it is important to evaluate the their compulsory missratio.
This paper shows the compulsory miss ratio when
the cache has no address entry. In addition, by using
both the compulsory and capacity miss ratios, we discuss the replacement policies of the cache entries, forfast recovery of packet reachability, when the cache has
unreachable address information.

We consider the HTTP accesses from the users accommodated by the same edge router. Let the total numberof HTTP accesses during a period be N , and the number of diﬀerent destination IP addresses appeared inthose N accesses be M . The relationship between N
and M is represented by the following three equations:


1
1
(1)
+ R(β−1)/β ,M =H γ + ln R +β
2 R1/β1
β−1
ln R +
N =R γ ++ H R1/β ,β
2 R(β−1)/β
(2)


1
N =R γ + ln M +,(3)2M
where R denotes the number of accesses to the most frequently accessed IP address, and H denotes the numberof IP addresses which are accessed only once. In addition, γ denotes the Euler number (γ  0.57721), andβ is a parameter (2.2 ≤ β ≤ 2.5) [4], [6]. The set ofthe above equations (1)–(3) is called the Dual Zipﬁan
Model (DZM) [4]. For example, if N is given, we canobtain the estimations of M , R, and H using Eqs. (1)–(3).
DZM is applicable for not only HTTP accesses but
also more realistic mixed packet stream which contains
HTTP, FTP, and SMTP e-mail at an edge router [4].
In cases of a backbone router or a WWW server, DZM
can be applied with some extension, too. We describe
those extension shortly in Appendix A.
Hereafter, we shortly denotes the relationship between N and M represented by Eqs. (1)–(3), as
M = f (N ).

(4)

2.2 Capacity Miss Ratio
Here, we review the derivations of the capacity missratio according to [4].
Let the capacity of the address cache (the maximum number of address entries) be k. When thecache does not contain the address, the edge router
requests corresponding address information to the address server, and the address information is written
over an entry of the address cache (Fig. 2). If all cache
entries are occupied by address information, new address information is written over an existing entry determined by an aging algorithm.
Diﬀerent aging algorithms give diﬀerent capacity
miss ratios, in general. In this paper, we consider thefollowing two classical aging algorithms:

IEICE TRANS. COMMUN., VOL.E83–B, NO.7 JULY 2000

1402

Fig. 3Fig. 2

Address cache model.

• Least Recently Used (LRU):
When the cache does not hit, new address data is
written over the least recently used entry.
• First In First Out (FIFO):
When the cache does not hit, new address data is
written over the current oldest entry.
For LRU, the address cache in the steady state
always has k diﬀerent IP addresses which are most recently accessed. The number of HTTP accesses that
requires resolution of k diﬀerent IP addresses is f −1 (k).
Similarly, the number of HTTP accesses that requires
resolution of k + 1 diﬀerent IP addresses is f −1 (k + 1).
Thus the number of HTTP accesses between two successive replacements of entries is f −1 (k + 1) − f −1 (k).
The capacity miss ratio for LRU, PL , is therefore obtained as
PL =1
f −1 (k + 1) − f −1 (k).

(5)

For FIFO, unlike LRU, the address cache does notalways have k diﬀerent IP addresses that are most recently accessed. Instead, let Nx be the number of accesses in the period during that all cache entries are
replaced. From [4], Nx must satisfy the following condition:
4 f (Nx ) − 3 k − 9 k2 − 8 k {f (2 Nx ) − f (Nx )}= 0.
(6)
If the capacity k is given, we can determine Nx by
Eq. (6). Thus, the capacity miss ratio for FIFO, PF ,is obtained as:
PF =
3.

k
.
Nx

(7)

Compulsory Miss Ratio

Here, we investigate the compulsory miss ratio of theaddress cache, i.e., the relationship between the number of accesses and the cache miss ration after voiding
all cache entries. In evaluation of the compulsory missratio, it is not necessary to take into consideration ofInterval of cache misses.

the diﬀerence of aging algorithms, e.g., LRU or FIFO.
The following discussion is applicable for any aging algorithms.
At the initial state, the address cache (its capacity is k address entries) has no address entry. For eachaccess, if the address cache does not hit, then the corresponding address data is written as an entry of thecache. When n accesses are happened from the initial state, the number of eﬀective entries of the address
cache is f (n) by DZM (Fig. 3). Note that range of n isbounded by f (n) ≤ k. The number of required accesses
between the time of n-th access and the time of the next
cache miss which brings a new valid cache entry is:f −1 (f (n) + 1) − n.

(8)Thus, the compulsory miss ratio, pc (n), at the time thatn accesses occur from the initial state, is obtained as
pc (n) =1
f −1 (f (n) + 1) − n.

(9)The form of the compulsory miss ratio (9) is basicallythe same to that of the capacity miss ratio for LRU(5), since any cache contains most recently accessed
addresses until the cache becomes full.
Next, we show the evaluation of the cumulative
compulsory miss ratio Pc (n). This is deﬁned as theratio of the number of cache misses to the number ofaccesses, from the initial state. The number of diﬀerent
IP addresses during n accesses is f (n). This is equal
to the total number of cache misses from the initialstate. Therefore, the cumulative compulsory miss ratio
is represented by
Pc (n) =

f (n)
.
n

(10)

Let us conﬁrm the relation between Eqs. (9) and (10).
We deﬁne a cumulative compulsory miss ratio between
the (n + 1)-th access and the m-th access (n < m) as:δc (n, m) =f (m) − f (n)
.
m−n

(11)

Equation (10) is actually a special case of Eq. (11)where n = 0, i.e.,δc (0, m) = Pc (m).

(12)

Furthermore, we can derive Eq. (9) from Eq. (11) byselecting m and n such that only one cache miss occurs
between those accesses:

AIDA et al.: EVALUATION OF COMPULSORY MISS RATIO FOR ADDRESS CACHE

1403

Fig. 4

Cumulative compulsory miss ratio (HTTP).

f (m) − f (n) = 1,

(13)

i.e.,
m = f −1 (1 + f (n)).

Fig. 5 Cumulative compulsory miss ratio (HTTP, FTP &SMTP e-mail).
Table 1 Comparison among schemes for restoring packet
reachability.

(14)
Purge operation
Natural recovery

By substituting Eq. (14) for Eq. (11), we have Eq. (9).
4.

LRU

FIFO

good
bad

moderate
good

Experimental Result

Although compulsory miss ratio (9) is an important
performance measure in actual applications, it is difﬁcult to compare it to experimental results, since thecache miss ratio changes instantaneously and is diﬃcult to measure. In order to verify the validity of thecompulsory miss ratio (9), we compare the cumulative
compulsory miss ratio (10) with experimental results.
If the validity of Eq. (10) is veriﬁed, Eq. (9) is also justiﬁed.
Figures 4 and 5 show the comparison between theestimated cumulative compulsory miss ratio (10) (denoted by solid lines) and experimental results (denotedby small square symbols). The vertical axis denotes the
cumulative compulsory miss ratio in log scale, and thehorizontal axis denotes the number of access from theinitial state. There is no address entry at the initialstate.
For Fig. 4, the experimental results come fromHTTP access logs of a WWW proxy server in NTT
Laboratories (about 100,000 accesses a day), and we
calculate the actual cumulative compulsory miss ratio
through trace-driven simulation using the logs. The
value of a parameter β in DZM is 2.30.
Figure 5 shows the comparison for the mixed traﬃcwhich contains HTTP, FTP and SMTP e-mail accesses.
Those accesses are also logged in NTT Laboratories.
The value of a parameter β in DZM is 2.35.
From these ﬁgures, we can recognize the cumulative compulsory miss ratio (10) gives dependable evaluations.

5.

Replacement Policies for Restoring Packet
Reachability

When a link trouble or a topology change of the network occurs, address information in the address cache
may lost its validity and cannot assure the packet reachability. In this situation, it is necessary to update thecorresponding cache entries. In this paper, we discuss
two schemes to update the invalid cache entries: full
purge and natural recovery. Accordingly the numberof possible combinations of aging algorithms (LRU and
FIFO) and the strategies are four (Table 1).
5.1 Purge Operation for Address Cache
A full purge operation is initiated by the address serverwhenever topology changes. After full purge at an address cache, there are no address entries in the cache.
The cache miss ratio jumps high instantly, then according with cache misses which actually increase thenumber of active cache entries, the cache miss ratio falls
gradually. This behavior of cache miss ratio is describedby the compulsory miss ratio (9). The address server
usually accommodate multiple edge routers, where eachof them has its own address cache. If the purge operations for multiple address caches are conducted simultaneously, the total amount of address resolution
inquiry may exceed the capacity of the address server.
To avoid this situation, it is necessary that multiple
address caches get fully purged not at once but by
turns. Interval between adjacent purge operations is

IEICE TRANS. COMMUN., VOL.E83–B, NO.7 JULY 2000

1404

determined by both the compulsory miss ratios of already purged caches and capacity miss ratios of theun-purged caches. Note that when multiple caches get
purged by turns, the address server have to handle resolution requests from not only purged caches but alsosteady caches which wait their turns to be purged.
Note that there can be another scheme which
purges invalid entries selectively (in contrast to full
purge which purges all, valid and invalid, entries atonce). This selective purge requires mechanisms tosearch the caches with invalid entries, and to search theinvalid entries in each of caches. The selective purge isout of scope of this paper since those mechanisms are
speciﬁc to network architecture protocols, and implementation.
Let us compare LRU and FIFO when purge operation scheme is used (Table 1). LRU is preferable to
FIFO by the following two reasons:• The capacity miss ratio for LRU is less than thatfor FIFO, and• The compulsory miss ratios for both LRU andFIFO are the same.
A purge operation itself is independent of the aging
algorithm to be used. Because LRU gives the smaller
capacity miss ratio, the address server can better focus
on the requests from purged caches and the time forcompleting all purge operations is shorter than that for
FIFO.
5.2 Natural Recovery of Packet Reachability
A Natural recovery (or self-heeling) strategy is to wait
simply until invalid entries are expired (over-written)
by the aging algorithm. With this strategy, the address cache keep steady operation with full entries andmaintain a relatively low cache miss ratio. However,the cache is not fully trustworthy since the invalid entries remain until they are written over by new address
information. For FIFO, each cache entry expires inturn and it is independent of the frequency of accesses.
Lifetime of the invalid entry to the number of accesses
is determined by Nx and it can be described by using
Eq. (6). On the other hand, for LRU, entry which isinvalid but accessed frequently may never be expired.
Thus, FIFO is preferable to LRU.
6.

Comparison between LRU/Purge
FIFO/Natural-Recovery

andFrom the above results, the two schemes, purge operation scheme with LRU and natural recovery schemewith FIFO, are preferred. This section shows the comparison between these two schemes with respect to fast
recovery of packet reachability. In addition, we reveal
applicable domains of them [8].
Figure 6 shows our system conﬁguration model.

Fig. 6

System conﬁguration.

There are 10 edge routers and an address server. Eachedge router has a address cache. All routers are assumed to have the same access rate. The address server
provides the following functions:• It has comprehensive address information.
• It adds address information to an address cachewhen the address cache miss occurs.
• It can conduct a purge operation to each address
cache.
Figure 7(a) shows the relationship between thehandling capacity of the address server and the numberof accesses which are occurred during the time intervalfrom the time purge for the ﬁrst cache begin to thetime purge for the last cache ﬁnished. The ﬁgure is calculated by the compulsory miss ration (9) and the capacity miss ratio (5). Interval between adjacent purge
operations is determined by both the compulsory missratios of already purged caches and capacity miss ratios of the caches waiting purge so that the load of theaddress server does not reach its capacity. We deﬁne
the handling capacity of the address server as the number of queries which can be process by the server inunit time. The capacity is 1 if the server can handle
all queries from just one address cache. The numberof accesses means the number of accesses on one edge
router. From Fig. 7(a), the purge scheme with LRU requires long time to complete when the capacity of theaddress server is low.
Figure 7(b) shows the relationship between the capacity of the address cache and the number of accesses
which are generated until completion of the natural recovery (i.e., all cache entries are replaced). This is simply determined by Nx in Eq. (6), since Nx is the number of accesses in the lifetime of an FIFO entry [4] The
number of accesses means the number of accesses on
one edge router. The ﬁgure shows the natural recovery
scheme with FIFO requires long time to recover cachevalidity when the capacity of address caches is large.
When the handling capacity of the address server islow, the natural recovery scheme with FIFO is preferable.

AIDA et al.: EVALUATION OF COMPULSORY MISS RATIO FOR ADDRESS CACHE

1405

(a)

(b)

Fig. 7 The number of accesses to recover reachability of packets. (a) Relationshipbetween handling capability of the address server and the number of accesses to thecompletion of purge operations. (b) Relationship between the capacity of the address
cache and the number of accesses to the natural recovery.

7.

Fig. 8

Applicable domains.

By combining the results from Figs. 7(a) and (b),Fig. 8 shows applicable domains for the two schemes.
The vertical axis denotes the handling capacity of theaddress server and the horizontal axis denotes the capacity of the address cache. Applicable domains are
determined by that which scheme can recover packet
reachability faster. Note that the applicable region fora purge operation with LRU does not spread under
the line such that the handling capacity of the address
server equals 1, and it is not only for our system conﬁguration but also for any system conﬁguration. Considering the performance of recent high-speed routers,
we think the handling capacity 1 of the address serveris a very high ﬁgure actually. Assuming the capacity of
the address server is less than 1 is safe in many cases,
where FIFO with natural recovery works better.

Conclusions

This paper have shown the evaluation of the compulsory miss ratio for the address cache and its application.
The evaluation is based on the Dual Zipﬁan Modeldescribing HTTP access trends. The validity of theevaluation is veriﬁed by comparison to experimental results.
Using the evaluation of the compulsory miss ratio, we have investigated some schemes restoring cachevalidity and their applicable regions. These schemes
are a purge operation and natural recovery with aging
algorithms.
Note that the applicable region for purge operation
spreads only where the handling capacity of the address
server is suﬃciently high. Some of recent high-speed
routers achieves packet throughput of 1 Mpps (packets
per second) or more. Address resolution by the address server using a large database of comprehensive
address information probably cannot keep up with thepacket throughput. The handling capacity of the address server to be over 1 is, therefore, unrealistic in ahigh-speed network using those high-speed routers.
The natural recovery scheme with FIFO is very
simpler than the other three schemes because FIFO issimpler than LRU and the natural recovery strategy is,of course, the simplest strategy. A high performanceaddress server is not required. It is a very interesting point that the natural recovery scheme with FIFO
is expected to work most eﬃciently among the otherschemes and is probably a solution in actual network
design.

IEICE TRANS. COMMUN., VOL.E83–B, NO.7 JULY 2000

1406

References[1] M. Laubach and J. Halpern, “Classical IP and ARP over
ATM,” RFC 2225, 1998.
[2] J.V. Luciani, D. Katz, D. Piscitello, B. Cole, and N. Doraswamy, “NBMA next hop resolution protocol (NHRP),”
RFC 2332, 1998.
[3] R. Jain, “Characteristics of destination address locality incomputer networks: A comparison of caching schemes,” DEC
Tech. Rep., DEC-TR-592, 1990.
[4] 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, 1998.
[5] S. Ata, M. Murata, and H. Miyahara, “Application of network traﬃc analysis for the design of high-speed routers,”
1999 IEICE TM Workshop, TMWS99-11, 1999.
[6] T. Abe and M. Aida, “Evaluation of address cache miss rateusing dual Zipﬁan model,” 1998 IEICE Society Conf., B-720, 1998.
[7] M. Aida and N. Takahashi, “Estimation of compulsory missratio for address cache using dual Zipﬁan model,” 1998
IEICE Society Conf., B-7-17, 1998.
[8] M. Matsuda and M. Aida, “Replacement policies of address
cache for restoring packet reachability,” 1998 IEICE Society
Conf., B-7-18, 1998.

Appendix A:

A.1

Analysis of the Access Logs ofthe WWW Servers and Extension of DZM

WWW Server-to-User Traﬃc

In this subsection, we analyze the access logs of the“NTT DIRECTORY” WWW servers† for October,1997. Those servers accepted in total over a million
accesses per day at the time. Through the analysis, we
see the characteristics of the server-to-user traﬃc.
The logs we used here are not the direct records
about server-to-user traﬃc, but are the records of user’s
requests for the web data on the servers. By using thoserecords of user-to-server requests, we can evaluate theserver-to-user traﬃc with the reasonable assumptions
as follow:• For each request from a user host, the WWW
server returns response to the host in some way(mostly requested data, sometimes an error information such as “We don’t have that data”). So,
we can count the source address of the request as
the destination of the server-to-user traﬃc. The
temporal order of the response is mostly same asthat of the request.
• One request could trigger multiple responses; text
data and graphic data, for example, are oftentransferred separately by each opening a TCP connection. With regard to analysis of the cachebehavior, since occurrence of those multiple responses are temporally close in most cases, we canFig. A· 1

Relation between m and R(m).

count those multiple responses as one series which
produce single address resolution (cache look-up)
process.
A.2

Relation between the Frequency of Destination
Addresses and the Number of Traﬃc Exchanges

Let us consider the ordering m of the destination IP
addresses of the transfers originated from the WWW
server, in descending order of the number of addresses;
i.e., we assign the most frequent destination address tom = 1, the second most frequent address to m = 2,
and so on. Then, let us deﬁne R(m) the number oftransfers sent out to the m-th most frequent address.
Figure A· 1 represents the distribution of the R(m) form in a logarithmic scale for the total traﬃc count of
10,000(10K), 30,000, 100,000, 300,000, 1,000,000(1M),and 3,000,000. The broken straight line indicates the
Zipf’s law with the slope −3/4. The distribution ofR(m) shows the good similarity regardless of the total
traﬃc count, and the Zipf’s law can be used to describe
the distribution well.
A.3

Relation between the Number of Destination Addresses and the Number of the Traﬃc Exchanges

Let us deﬁne H(n) the number of distinct addresses
where each address get exactly n transfers. Figure A· 2
represents the distribution of the H(n) for n in a logarithmic scale for the total traﬃc count of 10,000(10K),
30,000, 100,000, 300,000, 1,000,000(1M), and 3,000,000.
The distribution of H(n) shows the similarity among
the various case of the total traﬃc count. However,those curved lines of the distribution can not be paralleled by the straight line given by the conventional
usage of Zipf’s law. This means we can not directly apply the Zipf’s law here for the server-to-user traﬃc, incontrast to the user-to-server traﬃc which allows direct
application of the Zipf’s law [4].
†http://navi.ocn.ne.jp/

AIDA et al.: EVALUATION OF COMPULSORY MISS RATIO FOR ADDRESS CACHE

1407

Fig. A· 2

Relation between n and H(n).
Fig. A· 4

Fig. A· 3

Normalized relation between n and H(n).
Fig. A· 5

A.4

Upper-tail behavior of H(n).

Behavior of the Upper-Tail of H(n)The distribution of H(n) for n, where 1 ≤ n ≤ R(1),is 1 ≤ H(n) ≤ H(1). First we introduce the following
normalized form of H(n) and R(n):ln H(n)ln n, y :=x :=ln R(1)ln H(1)(A· 1)

such that x and y remain in 0 ≤ x, y ≤ 1 regardless ofn. Figure A· 3 shows the relation between x and y forvarious n of 30K, 300K, and 3M. Distributions for thediﬀerent n show a general similarity for the upper-tail(where n is less than about 0.4; the left half in Fig. A· 3)of the distributions.
To examine the upper-tail behavior, Fig. A· 4 gives
the relationship between x (horizontal axis) and 1 − y(vertical axis), in a logarithmic scale. The relation iswell ﬁt by the straight-line of slope 2, thus the following
relation stands:

2
ln n
ln H(n)(A· 2)− 1 = −aln H(1)ln R(1)

Approximation of the upper-tail behavior of H(n).

havior of H(n) can be described as follows: n 2
1−a lnln
R(1)H(n) = H(1)Figure A· 5 demonstrates the approximation described in this section, which has a form of y = 1−a x2 ,to the actual behavior of H(n) (for the total traﬃccount of 1M). The value of the parameter a is:a  10/3(A· 4)The upper-tail behavior of H(n) is approximated well.
A.5

Extension of Dual Zipﬁan Model

Let N be the total count of the traﬃc from the server
for the given time period, and M be the number of distinct destinations. By utilizing (A· 3), the Dual Zipﬁan
Model, Eqs. (1)–(3), is expressed extendedly as follows:R(1)1/β 

M = H



n=1

where a is a constant. Accordingly, the upper-tail be-(A· 3)

1
H

ln n
a( ln
R)

2

+ R(β−1)/(β ar ) (A· 5)

IEICE TRANS. COMMUN., VOL.E83–B, NO.7 JULY 2000

1408

Masaki Aida
received his B.S. and
M.S. degrees in Theoretical Physics from
St. Paul’s University, Tokyo, Japan, in
1987 and 1989, respectively, and received
the Ph.D. degree in Telecommunication
Engineering from 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 until March 1998. He
is currently a manager at Traﬃc Research Center, NTT Advanced Technology Corporation (NTT-AT). His current interests
include traﬃc issues in multimedia and mobile communication
systems. He received the Young Engineer Award of IEICE in
1996. Dr. Aida is a member of Operations Research Society ofJapan.
Fig. A· 6 Relationship between the traﬃc count and thenumber of destinations.
R(1)1/β 



N =H

n
H

n=1

ln n
a( ln
R)

R(β−1)/(β ar ) 

+R



m=1

2

1
mar

(A· 6)

M 

N =R



1
mar
m=1

(A· 7)

wherea  10/3, ar  3/4(A· 8)

stand and β is a parameter, and · denotes a ﬂoor
(integrize) operation.
The relationship between N and M are described
well by the extended Dual Zipﬁan Model (A· 5)–(A· 7),
as shown in Fig. A· 6. The horizontal axis is for N in alogarithmic scale, and the vertical one for M also in alogarithmic scale. β in this case is 2.30. Here stands
M = N 5/6
in the rough.

Noriyuki Takahashi
received his
B.S. and M.S. degrees in Information
Science from Kyoto University, Japan,
in 1990 and 1992, respectively.
Hejoined NTT LSI Laboratories in 1992,
where he has been conducting researchon computer-aided design/testing for LSI.
Since he joined NTT Information Sharing Platform Laboratories in 1996, he had
been mainly engaged in research on routing issues in IP-type networks. He is currently a research engineer at NTT Network Innovation Laboratories. His current interests include high-speed wide-area networking, multimedia communication. He is a member of IPSJ.

(A· 9)

Michiyo Matsuda
received her B.A.
degree in Modern History of Japan from
Kokugakuin University, Tokyo, Japan,
in 1992.
Since she joined NTT Advanced Technology Corporation (NTTAT) in 1992, she had been mainly engaged in research and development oncommunications software and distributed
caching systems. She is currently an assistant manager at Traﬃc Research Center,
NTT-AT.