IEICE TRANS. COMMUN., VOL.E87–B, NO.1 JANUARY 2004

132

PAPER

Capacity Dimensioning of VPN Access Links for Elastic
Traﬃc in the Hose Model
Keisuke ISHIBASHI†a) , Mika ISHIZUKA† , Masaki AIDA† ,and Shin-ichi KURIBAYASHI† , Members

SUMMARY This paper discusses research into the capacity
dimensioning of Virtual Private Network (VPN) access links forelastic traﬃc, such as the Web or ftp. Assuming that the coreVPN network is provisioned with a suﬃciently large capacity,managing the capacity of the VPN access link comes to sharing the bandwidth for the elastic traﬃc of the two bottlenecks,
the ingress and egress access links. In the case of a single bottleneck with a limited capacity for access links, the processorsharing model provides a simple formula for mean transfer time,
but here, the value may be less than the actual transfer time because multiple ﬂow may compete the bandwidth of both ingressand egress links. In contrast, max-min fair sharing provides anaccurate sharing model which is similar to the TCP, but it isdiﬃcult to obtain a closed form for performance statistics. We
propose a closed form approximation for a max-min fair sharing model, within a speciﬁc but realistic topology, through aninvestigation into the diﬀerence between the max-min and theprocessor sharing model. Using approximation, we calculate thecapacity dimensioning of VPN access links.
key words: VPN, hose model, max-min fair sharing

1.

Introduction

Virtual Private Networks (VPNs) are widely usedbecause they provide secure connections between
customer-LANs at reasonable cost. The VPN service
model is divided into two categories: the customer pipe
model and the hose model [1].
The customer pipe model is an emulation of aleased lines. Using this model, the customer needs toprepare individual customer pipes for every pair of customer LANs. Traﬃc from one LAN to other LANs
is separated among corresponding pipes. Traﬃc engineering for this model is essentially the same as thatfor leased lines. On the other hand, in the hose model,
the customer only needs to prepare an access link to
the VPN core network from each customer LAN, noteach pair of LANs∗ . Traﬃc from the LAN to all otherLANs is aggregated into the link. From the customer’s
point of view, one of the advantages of the hose model
is its statistical multiplexing gain at the access link.
Duﬃeld et al. evaluated the gain using the actual
traﬃc data of corporate network [1]. They allocatedManuscript received April 2, 2003.
Manuscript revised August 13, 2003.
†
The authors are with the NTT Information Sharing
Platform Laboratories, NTT Corporation, Musashino-shi,
180-8585 Japan.
a) E-mail: ishibashi.keisuke@lab.ntt.co.jp

the capacity based on the peak rate, and stated thatthe capacity could be reduced by 6.5% up to 72%. Lee
et al. also studied the gain by calculating the capacity
to meet given packet loss probability [4]. They useda sample traﬃc matrix and showed the gain was from
16% to 42%. In our paper, we focus on ﬂow level performance, such as the mean transfer time for TCP traﬃcin dimensioning access-link capacity. Because a large
portion of current traﬃc is TCP [3], it is adequate toconsider performance at the TCP ﬂow level for capacity
dimensioning.
To evaluate the performance of TCP ﬂow, we must
consider both the core network, provisioned by theprovider and the access network provisioned by the customer. However, providers normally provision a core
network with suﬃcient capacity so that the network
cannot or rarely becomes a bottleneck [1], [5]. Therefore, we can assume that the user can fully utilize thecapacity of their access links. Based on this assumption, traﬃc engineering for the VPN access link becomes a bandwidth-sharing problem for elastic traﬃcthat goes through two bottlenecks: the ingress andegress access links.
In this paper, we consider the case of a networkthat consists of one central LAN and multiple branchLANs (“star-topology”), which is the most typical network topology for VPN of enterprises which consists
one central oﬃce and several branch oﬃces, and whereelastic traﬃc is transferred between the central LAN
and branch LANs (Fig. 1). We can expect to obtain astatistical multiplexing gain for the access link of thecentral LAN, where many ﬂows from/to other branchLANs share the bandwidth.
Many papers have addressed TCP bandwidth sharing issues using the processor sharing model [6], [9]–[12]. In this model, ﬂows share the bandwidth equallyand the throughput is equal to the capacity divided by
the number of competing ﬂows. When a ﬂow cannnot
utilize the capacity itself due to the rate-limited accesslink, the throughput of a ﬂow is determined by the min∗More precisely pipe model speciﬁes the traﬃc/QoS requirements for each pair of LANs and the hose model speciﬁes the requirements for each LAN and core network. But,in this paper, we have considered the minimum bandwidth
guarantee for QoS and identify the guranteed bandwidth as
the physical bandwidth for access links.

ISHIBASHI et al.: CAPACITY DIMENSIONING OF VPN ACCESS LINKS FOR ELASTIC TRAFFIC IN THE HOSE MODEL

133

Finally, we provide methods for capacity dimensioningof access links, using the approximation in Sect. 4.
2.

Bandwidth Sharing for VPN Access Links

2.1 Bandwidth Sharing—Processor Sharing and MaxMin Sharing

Fig. 1

Hose model VPN.

imum of the equally-shared bandwidth of a bottleneck
link and the bandwidth of an access link. In this model,
the performance index such as mean transfer time canbe calculated using the capacity and utilization ratio
for a Poisson arrival case. It should be mentioned thatthe indexes are independent of the ﬁle size distribution.
It seems that this model can be applied to our case,because access links with limited capacity in the model
correspond to branch-LAN access links, and the bottleneck link where many ﬂows compete for its bandwidthcorresponds to the central-LAN access link in our case.
However, because this model does not consider when
multiple ﬂows compete with the access link of a branchLAN, the mean transfer time for VPN access may beunderestimated when applied to our scenario.
In terms of multiple bottleneck links, there aremany papers that deal with TCP ﬂows that share thebandwidth of links with max-min fair sharing or proportional sharing for general topology [15]–[18].
Most of these consider persistent ﬂow i.e., the number of ﬂows remain ﬁxed, but some deal with a variable
number of ﬂows expressed as a random variable [18],[19], where max-min sharing is presumed. However, because the exact mean transfer time for max-min sharing is diﬃcult to derive, they propose approximationsof sharing. While these approximations can be applied
to general topology, both Chanda and Fayolle et al.’results do not have suﬃcient accuracy for the capacity
dimensioning.
In this paper, we assume that TCP shares bandwidth according to max-min fair sharing and we propose an accurate approximation of performance for star
topology by focusing on the diﬀerence between maxmin sharing and processor sharing with a narrow accesslink. Using this approximation, we provide some examples of methods for the capacity dimensioning of VPN
access links to achieve various performance objectives.
The rest of the paper is organized as follows. We
begin by describing conditions this paper concerned andobserving some bandwidth sharing models. We also
provide an approximation in Sect. 2. Section 3 evaluates the approximation in various network scenarios.

In this subsection, we compare two bandwidth sharing
policies: processor sharing with an access link of limited
capacity and max-min sharing.
Let us describe the conditions we have assumed inthis paper.
• A customer VPN consists of one central LAN,
whose access-link capacity is C [bps] and k branchLANs, whose access-link capacity is r [bps]. (Thereis a homogeneous environment among branch
LANs.) The capacity of LANs and the core network are suﬃciently large so that these networks
cannot become bottlenecked.
• Traﬃc type is TCP ﬁle transfer between the central
LAN and k branch LANs.
• Flow-arrival process is Poisson [22] with arrival
rate λ [1/s] for each branch-LAN (for central-LAN,
arrival rate is kλ).
• File size is exponentially distributed and its mean
is s [bits].
• Mean ﬁle size is suﬃciently large so that we can ignore slow-start eﬀect, and ﬂow achieves fair sharing
instantaneously.
• Window size is suﬃciently large so that a ﬂow canutilize access-link capacity when there are no otherﬂows within the link.
• The performance criterion is the mean transfer
time.
We also prepared notations of utilization for thecentral-LAN access link that are ρC := kλs/C and thatfor branch-LANs as ρr := λs/r. Using these notations,multiplex gain for central-LAN access links can be evaluated with (kr − C)/C.
According to the processor sharing model with limited capacity, r [bps], available bandwidth for a ﬂow
is determined depending on the number of competing ﬂows in a central-LAN access link, and equals
min(C/n, r), where n is the number of ﬂows in thecentral-LAN access link at a point of time. Then, themean transfer time under the processor sharing policy,
TPS , is calculated for general distributed ﬁle size [12] as
TPS (C, ρr )




C
1
E2,R (kρr )=s+
1 − (1 − ρC )−R,
r
(1 − ρC )Cr(1)
where R =  Cr  and E2,R (kρr ) is Erlang’s C formula[20], which can be written as:

IEICE TRANS. COMMUN., VOL.E87–B, NO.1 JANUARY 2004

134


E2,R (kρr ) :=(kρr )RR!

R−1 (kρr )k
+
k=0
k!




1
1−ρr

(kρr )R
R!




1
1−ρr

.
(2)

However, this result cannot be directly applied toour case. This is because when multiple ﬂows share anaccess link of a branch-LAN, a ﬂow cannot utilize thefull bandwidth of the access-link as ﬂows compete forthe bandwidth, and the available bandwidth is smaller
than min(C/n, r).
On the other hand, according to the max-min
model, multiple ﬂows in a branch-LAN access link areconsidered. In the model, the available bandwidth fora ﬂow in i-th branch-LAN bi (N ) is determined not only
by n, but also by state vector N = {ni }ki=1 whose element ni is the number of ﬂows for the i-th branch-LAN
access link as follows [21]. First, without loss of generality, suppose that the index is descendingly ordered byni , i.e., ni ≥ ni+1 . Let g = ki=1 1{ni >0} (number ofbranch-LANs that has at least one ﬂow to central-LAN)and n0 = 0.

Table 1 Evaluation conditions.
k (number of branch-LANs)10
r (bandwidth branch-LAN link)
1.5 Mbpss (mean ﬁle size)
1 Mbyteρr (utlization ratio for branch-LAN)
0.2, 0.4, 0.6, and 0.8

Fig. 2 Distribution of number of ﬂows for ρr = 0.4 and C =7.5 [Mbps].

Step 1: Let i = 1.
Step 2: If
C − (i − 1)r
r
≤
.
i−1
ni
n − j=0nj(3)then go to Step 3. Otherwise for ﬂows in branchLANs i, i + 1, . . . g, the available bandwidth is limited by the capacity of the central-LAN access-link,andbl (N ) =C − (i − 1)rn−i−1
j=0 nj,l = i, . . . , g.

(4)

Stop the procedure.
Step 3: Access link for branch i is bottlenecked andbi (N ) = r/ni . Set i ← i + 1 and return to Step 2.
To see which sharing policy represents the TCP
bandwidth sharing mechanism, we compared the performance obtained by the processor sharing model using (1), the max-min model and ns simulation [23] as areference for TCP performance. Because it is diﬃcult
to obtain a closed form for performance statistics forthe max-min model, we ran simulations of the Markov
process for N including 100,000 transissions where
the departure rate-vector is given as {ni bi (N )/s}ki=1 .
Through the simulations, we obtained a mean of n fromwhich we calculated the mean transfer time using Little’s Law [20]. The parameter set used here is listed inTable 1.
For ns simulations, we set the propagation delay
for an access link to 10 ms, with a maximum window
size of 20 kbytes, and the number of terminals in abranch LAN to 100. The core network was represented
by a single node. We set the buﬀer size of every routerFig. 3

Mean transfer time for ρr = 0.2.

to 10,000 packets so that we could consider that routers
had inﬁnitely large buﬀers.
We used TCP Tahoe for the simulation† . We ran
ﬁve simulations each lasting 36, 000-s and derived average and 95% conﬁdence intervals.
Figure 2 shows the distribution of n when the utilization ratio ρr is 0.4 and C = 7.5 Mbps. We foundthat while the max-min sharing model and TCP agree
in the distribution, the processor-sharing model has amass probability with lower n than TCP.
†

The mean transfer time with TCP Tahoe may be larger
than those with TCP Reno or TCP SACK particularly when
packet loss occurs [24], [25]. And the max-min model gives
the minimum mean ﬁle transfer time because it assumes
that a ﬂow can fully utilize the available bandwidth. In
our case, as will be seen later (espesially in Sect. 3.4 where
packet loss occurs), the mean ﬁle transfer time with TCP
Tahoe is roughly as same as those with the max-min model.
Thus the mean ﬁle transfer time with TCP Reno or SACK
is also expected to be approximately same as those with themax-min model.

ISHIBASHI et al.: CAPACITY DIMENSIONING OF VPN ACCESS LINKS FOR ELASTIC TRAFFIC IN THE HOSE MODEL

135

in our scenario where a TCP ﬂow fairly shares the bandwidth among other competing ﬂows. This is the condition that RTT is small and mean ﬁle size are suﬃciently
large.
In general, however, the max-min sharing model is
not tractable to obtain a closed form of the stationary
distribution for the number of ﬂows or mean transfer
time [7], [18], [19]. In the next subsection, we propose
an approximation for the mean transfer time using TPS .
2.2 Approximation of Mean Transfer Time
Fig. 4

Mean transfer time for ρr = 0.4.

To derive an approximation of TMM using TPS , let us
ﬁrst describe the diﬀerence between TMM and TPS for
several special cases.
(A) In general, when C = r, the access links of branchLANs cannot be bottlenecked, and the access linkof the central LAN is the only single bottleneck forthe network. Thus, the performance of the maxmin model is the same as that of the processorsharing model because it assumes equal bandwidth
sharing among ﬂows for a single-bottleneck case.
1 (Ckrρr ) and ρr < 1, both perWhen ρCformance outcomes also agree becausebi (N ) → C/n, as ρC → 1.

Fig. 5

Mean transfer time for ρr = 0.6.

(5)(B) When C = kr, then in the max-min model, thecentral-LAN access link is no longer bottlenecked,
and TMM (kr, ρr ) = TMM (∞, ρr ).
(C) When C = ∞, then available bandwidth for theprocessor-sharing model min(C/n, r) = r, thus themodel derives s/r as a mean transfer time. On
the other hand, the available bandwidth throughthe max-min sharing model is r/ni . By applying
processor sharing for each access link for branch
LAN independently, we derive the mean transfers[7]. Thus, TMM (∞, ρr ) is 1/(1−ρr )time as r(1−ρr)
times larger than TPS (∞, ρr ).
To explore TMM in general cases, we deﬁned the(C,ρr )and plotcompensation formula F (C, ρr ) := TTMM
PS (C,ρr )Fig. 6

Mean transfer time for ρr = 0.8.

Figures 3–6 have the mean transfer time forTCP (TTCP (C, ρr )), the processor-sharing model(TPS (C, ρr )), and the max-min model (TMM (C, ρr ))with respect to the capacity of central-LAN accesslinks. From these ﬁgures, we can see that when ρr ishigh and C is large, there is considerable discrepancy
between TPS and TTCP .
In contrast, with the max-min sharing model, both
the distribution of the number of ﬂows and the meantransfer time are very similar to TCP results.
Thus, we can consider the performance obtained
through the max-min model as the actual performance1− F (C, ρr )1 − ρr(6)

for several ρr against C semi-logarithmically (Fig. 7).
From the above condition (C), we expected that(6) would approach to 0 as C increases. In addition,from Fig. 7, we observed that (6) decayed exponentially
as C increased for every ρr . Thus, we expected that
F (C, ρr ) can be written as
F (C, ρr ) ≈1− α exp(−βC).
1 − ρr(7)

Then parameters α and β can be calculated using conditions (A) and (B). Here, we calculated α and β when

IEICE TRANS. COMMUN., VOL.E87–B, NO.1 JANUARY 2004

136

Fig. 7

1
Plot of 1−ρ− F (C, ρr ).

Fig. 8

Approximated mean transfer time.

kρr > 1 (C = r means ρC > 1). Then from condition(A), we derive
α exp(−βkρr r) = 1.

(8)

From condition (B), we derive
α exp(−βkr) =s 1 − ρr.
r TPS (kr, ρr )(9)

Therefore, we have an approximation F  (C, ρr ) of
F (C, ρr ) as follows:r C/kr−ρ
1−ρr
s/r
1
−
1
ρ
TPS (kr,ρr )rF  (C, ρr ) :=−.
1 − ρr1 − ρrρr(10)
Thus, the approximated mean transfer time TAPX isgiven using TPS , which can be given in closed form, as
TAPX (C, ρr ) := TPS (C, ρr )F  (C, ρr ).
3.

(11)

Simulation Results

In this section, we evaluated the approximation (11) for
various environments. The reference transfer time for
TCP was obtained through ns-simulations as well.
3.1 Conditions in Sect. 2
We ﬁrst evaluated the conditions used in Sect. 2. We
plotted the mean transfer time obtained with (11) for
the situations used in Sect. 2 (Fig. 8). As a natural
expectation from the results of Fig. 7, it can be foundthat the (11) approximates TCP performance well, evenwhen utilization is high.
3.2 Pareto Distributed File SizeWe also evaluated our approximation with a Pareto distributed ﬁle size. Because the processor-sharing model,
which our approximation agrees with in extreme cases,

Fig. 9Mean transfer time for Pareto distributed ﬁle size.

proved to be insensitive to the distribution of ﬁle size[26], we expected that our approximation would also
be insensitive. Figure 9 shows the mean transfer timefor Pareto distribution and our approximation for the
shape parameter 1.5. Though the ﬁt is not as good as
those for the exponential case, it can be said that (11)can also approximate performance for Pareto distribution. The deviation of TTCP from TAPX was considered
to mainly derive from the large variation in ﬁle transfer
time due to heavy tail distribution of ﬁle size.
3.3 Small File Size
We changed the mean ﬁle size from 1,000 KB to 50 KB
to access the eﬀect of TCP’s initial slow start on meantransfer time Figures 10–13 have the mean transfer time
for the hose model, the approximation of time for thehose model, and the time for the pipe model. We cansee that there are non-negligible diﬀerences between
actual transfer time and approximated transfer time.
Several papers [13], [14], [27] pointed out this diﬀerence
for the processor sharing model and proposed ways tocompensate for this diﬀerence. For example, Ozawa
proposed adding delay for slow-start phase to the transfer time calculated with PS model in [13].
Thus, if we use the approximation formula (11) to
calculate the exact mean transfer time for small ﬁles, weISHIBASHI et al.: CAPACITY DIMENSIONING OF VPN ACCESS LINKS FOR ELASTIC TRAFFIC IN THE HOSE MODEL

137

Fig. 100.2).

Mean transfer time for 50 KB average ﬁle size (ρr =Fig. 130.8).

Mean transfer time for 50 KB average ﬁle size (ρr =Fig. 11
0.4).

Mean transfer time for 50 KB average ﬁle size (ρr =Fig. 14 Relative error of the approximation for various meanﬁle size when C is ﬁxed to 15 [Mbps].

for small ﬁles.
We also investigate the relative error of our approximation for various mean ﬂow sizes (Fig. 14). We
set capacity of central LAN access link (C) as 15 Mbps,
where the slow start eﬀects are largest as can be seenfrom Figs. 10–13 (For C larger than 15 Mbps, the meantransfer time will be the same as 15 Mbps case). From
the ﬁgure, we can see that slow-start eﬀect is negligble
when mean ﬁle size is larger than 500 KB.
3.4 Small Buﬀer SizeFig. 12
0.6).

Mean transfer time for 50 KB average ﬁle size (ρr =should introduce this compensation into our formula.
Note that the mean transfer time for the pipe
model also increased due to the slow start eﬀect(without slow start, the transfer time should equal
TAPX (15, ρr )). Thus, even for small ﬁles, the approximation formula (11) may suﬃce for the capacity dimensioning method where a capacity for the hose model iscalculated to achieve the same mean transfer time asthat for the pipe model. Section 4 presents the results obtained from simulating capacity dimensioning

So far, we have evaluated for the buﬀer size of 10,000
packet case, where no packet loss occured. Here, wechanged the buﬀer size to 50 packet and ran simulations to see the eﬀect of packet losses (Fig. 15). We cansee that in the case for narrow capacity of central-LAN
access links, actual TCP transfer time was longer than
the approximated transfer time (TAPX ), which was calculated using nominal utilization ratio (utilization ratio
calculated with the input parameter of the simulations).
Followings can be considered as the reasons of this increase:• due to the slow start after packet losses, the bandwidth may not fully utilized

IEICE TRANS. COMMUN., VOL.E87–B, NO.1 JANUARY 2004

138

Fig. 15

Mean transfer time for 50 packet buﬀer.
Fig. 16• actual utilization ratio may increase due to the retransmisions after packet losses.
To eliminate the latter eﬀect, we also calculate approximated mean transfer time using acutal utilizatoin ratio(TAPX (actual)). We can see that TCP transfer time
can fairly be approximated by using the actual utilization ratio, which can be obtaind through easy traﬃcmeasurement.
3.5 Heterogenous Access Links
Until now, we have only evaluated our approximation
formula (11) in a homogenous access environment. In
this subsection, we test this formula in a heterogenous
access environment. We derive the approximation formula on the basis of two processor sharing models for
extreme cases, the M/G/1/PS for C = kr case and the
M/G/R/PS for C krρr case. The mean transfer time
for the M/G/1/PS model is calculated independently
for each access link, thus heterogenity does not matter. However, the M/G/R/PS model, where multiple
ﬂows share the bandwidth of central-LAN access links,
has not yet been completely extended to heterogenous
access links, to the best of our knowledge. Lindberger
suggested that by using the average capacity of accesslinks weighted by its utilization ratio in place of r in (1),the mean transfer time could be roughly approximated[28], [29]. However, the number of diﬀerent access links
is limited to two types in deriviating the approximation. Thus, our formula cannot be directly extended toa heterogenous environment due to the lack of a basicmodel. Let us now discuss how the heterogenity aﬀects
mean transfer time.
Figure 16 has the mean transfer time for multiple access capacity, one 3 Mbps, two 2.25 Mbps, three
1.5 Mbps and four 0.75 Mbps links (1.5 Mbps on average) and its approximation assuming the bandwidthof all access links is 1.5 Mbps (mean transfer times forthe simulation results and approximation will be thesame for C = kr). As expected, there is a diﬀerencekrρr . However, exbetween TAPX and TTCP for C
cept for this extreme case, our approximation, assuming

Mean transfer time for multiple access capacity.

homogenous access links, can predict the actual meantransfer time fairly well and can be applied to this network environment.
4.

Capacity Dimensioning

This section presents two example methods for capacity
dimensioning of VPN access links using the approximation given in Sect. 2.
We ﬁrst ﬁx the capacity for a branch LAN, andcalculate the required capacity of the access to the central LAN to achieve the target mean transfer time. The
target was set as γ (> 1) times the quantity of the meantransfer time obtained from the pipe model where thecapacity of the pipe was conﬁgured the same as for the
branch LAN access link. Note that the mean transfer
time for γ = 1 cannot be achieved if the capacity of the
branch LAN is the same as the pipe model and C < kr.
This capacity is given using (11) as follows:
 

γs

(12)
Cr := min C  TAPX (C, ρr ) ≤r(1 − ρr )We calculated Cr for γ = 1.1 and ρr = 0.2, 0.4, 0.6,
and 0.8 for the same environment in Sect. 2. Figure 17
shows the results. We also calculate the required capacity using TTCP . We found that using our approximation, the required capacity could be calculated accurately and multiplexing gain kr/Cr was large when
the utilization of branch LAN, ρr , was low.
As another example, we set γ = 1 and increased
the capacity for branch LANs, r. Then, given the capacity for branch LANs, we determined the required
capacity for the central LAN, Cr .
In this example, as r increases, the Cr to achieve
the same mean transfer time for the pipe model decreases, and the degree-of-freedom increases.
Thus, to determine capacities, we intoduce a
cost function P (·) of capacity, which is, for example,
monthly fee for the access link determined by its capacity.
Then, we seek the capacity of the branch LAN that

ISHIBASHI et al.: CAPACITY DIMENSIONING OF VPN ACCESS LINKS FOR ELASTIC TRAFFIC IN THE HOSE MODEL

139
Table 2

Fig. 17 Required capacity to achieve the objective
performance.

Fig. 18

Total required capacity (kr + Cr ) for hose model.

would minimize the total cost asr ∗ = argmin kP (r) + P (Cr ).
r(13)

When the cost function P is linear and non-decreasing[30], then (13) is equivalent tor ∗ = argmin kr + Crr

(14)

Figure 18 show the total required capacity (=kr + Cr ) changing the capacity of branch-LAN accesslinks. We see that the total required capacity take its
minimum for r at about 1.6 Mbps.
Thus, by increasing the bandwidth of branch-LAN
access links by about 5%, we can decrease the totalrequired bandwidth, for example, by about 26% whenρr = 0.2. We observed that the total required capacity
was small for a low utilization ratio, and increased as
the utilization ratio increased, the same as for Fig. 17.
Of course these values depend on the condition such as
the number of branch LAN. However, we can numerically evaluate the relationship between the increase ofbranch-LAN access links and the decrease of the totalrequired bandwidth using our method.
From Table 2, we can also see that r ∗ , optimal
capacity for branch LAN access links, take its minimumat ρr = 0.4. However, because we have not yet derived
a formulae that derives r ∗ as a closed form, we cannnot

Simulation results for r ∗ and Cr∗ .

ρr

0.2

0.4

0.6

0.8

r ∗ (Mbps)
Cr∗ (Mbps)
kr ∗ + Cr∗ (Mbps)
r ∗ (with PS) (Mbps)
Cr∗ (with PS) (Mbps)
kr + Cr∗ (with PS) (Mbps)
TPipe (50 KB) (s)TMin (50 KB) (s)TMin (50 KB) (with PS) (s)TAPX (50 KB) (s)TPipe (1,000 KB) (s)TMin (1,000 KB) (s)TMin (1,000 KB) (with PS) (s)TAPX (1,000 KB) (s)

1.58
6.27
22.0
1.50
5.04
20.0
0.495
0.496
0.55
0.333
6.61
6.60
7.79
6.67

1.67
8.75
25.4
1.50
7.34
22.3
0.608
0.601
0.76
0.444
8.96
8.64
11.6
8.89

1.58
11.00
26.8
1.50
9.79
24.8
0.833
0.826
1.20
0.667
12.9
12.9
18.8
13.3

1.55
13.01
28.5
1.50
12.3
27.3
1.50
1.54
3.28
1.33
26.5
25.5
40.4
26.7

tell directly how r∗ changes as a function of ρr .
To prove the eﬀectiveness of the dimensioning
method, we ran simulations for the hose model where
the bandwidth of branch-LAN and central LAN access links were r ∗ and Cr∗ , and for the pipe model
where pipe bandwidth is 1.5 Mbps. Two mean ﬁle sizes,
1, 000 KB and 50 KB, were evaluated. The other simulation conditions were the same as in Sect. 2. We compared the mean transfer time obtaind through the hosewith r ∗ and Cr∗ simulation results (which are denoted
as TMin ), pipe simulation results (which are denoted as
TPipe ), and those calculated the approximation formulae for C = kr case (TAPX ). Note that TAPX shouldbe equal to those for the pipe model if TCP strictly
achives max-min sharing (without slowstart). Table 2
shows the results. We can see that the mean transfer
time for the dimensioning method was almost the sameas that for the pipe model. It should be mentioned thatwhile TMin was larger than TAPX for a 50-KB ﬁle size,
the above equation still held, as indicated in Sect. 3.
We also calculate r ∗ and C ∗ using PS model andevaluate the mean transfer time through simulations
using these bandwidth. The results are shown in Table 2 with the notation “(with PS).” As is expectedfrom Figs. 3–6, calculated bandwidthes with PS model
are smaller than those with the proposed approximation formulae. As a result, the mean transfer time increases, especially when high utilization ratio.
5.

Conclusion

We considered capacity dimensioning for VPN accesslinks for elastic traﬃc with star topology. We conﬁrmedthat the simple processor sharing model could not beapplied to our case, and the max-min sharing model
was able to predict TCP performance. Because the exact calculation of performance is diﬃcult, we proposeda closed form approximation of max-min fair sharing.
The approximation was derived by considering the difference between processor sharing and max-min sharing
models. We discussed two methods of dimensioning us-

IEICE TRANS. COMMUN., VOL.E87–B, NO.1 JANUARY 2004

140

ing the approximation.
Our work currently focus on only TCP traﬃc. Current traﬃc includes both TCP and UDP traﬃc. Inthat case, our method cannot be applied diretly to capacity dimensioning. And modiﬁcation of our method
to those case remains for further study. However, arough estimate of required capacity can be calculated
by adding capacity for UDP traﬃc to that calculated byour method, because UDP does not have any congestion control mechanism and its traﬃc tends to utilize
bandwidth as possible.
Acknowledgements
We would like to thank Dr. Ryoichi Kawahara for his
valuable comments and Ms. Kyoko Ashitagawa for her
help with the simulations.
References[1] N.G. Duﬃeld, P. Goyal, and A. Greenberg, “A ﬂexible
model for resource management in virtual private networks,” Proc. ACM SIGCOMM’99, 1999.
[2] B. Davie and Y. Rekhter, MPLS: Technology and applications, Morgan Kaufmann, San Francisco, 2000.
[3] K. Thompson, G.J. Miller, and R. Wilder, “Wide-area Internet traﬃc patterns and characteristics,” IEEE Netw.,
Nov./Dec. 1997.
[4] H. Lee, Y. Uh, M.-T. Hwang, J.-H. Eom, Y.-G. Lee, and
Y. Nemoto, “Capacity design of guaranteed-QoS VPN,”IEICE Trans. Commun., vol.E85-B, no.5, pp.1042–1045,
May 2002.
[5] A. Kumar, R. Rastogi, A. Silberschatz, and B. Yener, “Algorithms for provisioning virtual private networks in thehose model,” Proc. ACM SIGCOMM’01, 2001.
[6] M. Nabe, M. Murata, and H. Miyahara, “Analysis and modeling of World Wide Web traﬃc for capacity dimensioningof Internet access lines,” Performance Evaluation, vol.34,
no.4, 1998.
[7] J.W. Roberts and L. Massoule, “Bandwidth sharing andadmission control for elastic traﬃc,” Proc. ITC Specialist
Seminar 1998.
[8] A.W. Berger and Y. Kogan, “Dimensioning bandwidth forelastic traﬃc in high-speed data networks,” IEEE/ACM
Trans. Netw., vol.8, no.5, pp.643–654, 2000.
[9] D.P. Heyman, T.V. Lakshman, and A.L. Neidhardt, “A
new method for analysing feedback-based protocols withapplications to engineering web traﬃc over the Internet,”
Proc. ACM SIGMETRICS’97, 1997.
[10] A. Riedl, T. Bauschert, M. Perske, and A. Probst, “Investigation of the M/G/R processor sharing model for dimensioning of IP access networks with elastic traﬃc,” Proc.
First Polish-German Teletraﬃc Symposium, 2000.
[11] J.V.L. Beckers, I. Hendrawan, R.E. Kooij, and R.D. van derMei, “Generalized processor sharing performance models
for Internet access lines,” Proc. 9th IFIP Conf. on Performance Modelling and Evaluation of ATM & IP Networks,
2001.
[12] S.B. Fredj, T. Bonald, A. Proutiere, G. Regnie, and J.W.
Roberts, “Statistical bandwidth sharing: A study of congestion at ﬂow level,” Proc. ACM SIGCOMM’01, 2001.
[13] T. Ozawa, “Analysis of the mean response time using a processor sharing model,” IEICE Technical Report, NS200212, 2002.

[14] M. Fukushima, H. Nakamura, and S. Nomoto, “A study ona model of bandwidth sharing among multiple TCP connections with slow start,” Proc. IEICE-CS Conf. IEICE2002,
SB-13-3, 2002.
[15] L. Massoulie and J. Roberts, “Bandwidth sharing: Objectives and algorithms,” IEEE/ACM Trans. Netw., vol.10,
no.3, pp.320–328, 2002.
[16] T. Bonald and L. Massoulie, “Impact of fairness on Internet
performance,” Proc. ACM SIGMETRICS’01, 2001.
[17] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Trans. Netw., vol.8, no.5,
pp.556–567, 2000.
[18] P.S. Chanda, A. Kumar, and A.A. Kherani, “An approximate calculation of max-min fair throughputs for
non-persistent elastic ﬂows,” Proc. IEEE GLOBECOM’01,
2001.
[19] G. Fayolle, A. Fortelle, J.-M. Lasgouttes, L. Massoulie,
and J. Roberts, “Best-eﬀort networks: Modeling and performance analysis via large networks asymptotics,” Proc.
IEEE INFOCOM’01, 2001.
[20] L. Kleinrock, Queuing Systems, vol.1, John Wiley & Sons,
New York, 1976.
[21] D. Bertsekas and R. Gallager, Data Networks, 2nd ed.,Prentice-Hall, Upper Saddle River, NJ, 1992.
[22] V. Paxon and S. Floyd, “Wide-area traﬃc: The failure ofPoisson modeling,” IEEE/ACM Trans. Netw., vol.3, no.3,
pp.226–244, June 1995.
[23] UCB/LBNL/VINT Network Simulator—ns (version 2).
http://www.isi.edu/nsnam/ns.
[24] K. Fall and S. Floyd, “Simulation-based comparisons of
Tahoe, Reno and SACK TCP,” ACM SIGCOMM Computer Communication Review, vol.26, no.3, July 1996.
[25] G. Hasegawa, M. Murata, and H. Miyahara, “Fairness
and stability of congestion control mechanisms of TCP,”
Telecommunication Systems Journal, pp.167–184, Nov.
2000.
[26] F.P. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, New York, 1979.
[27] A.A. Kherani and A. Kumar, “Stochastic models forthroughput analysis of randomly arriving elastic ﬂows in
the Internet,” Proc. IEEE INFOCOM’02, 2002.
[28] K. Lindberger, “Delays in ABR-like traﬃc and relations toprocessor sharing,” COST 257 TD(98) 10, 1998.
[29] K. Lindberger, “Balancing quality of service, pricing andutilization in multiservice networks with stream and elastic
traﬃc,” Proc. ITC 16, 1999.
[30] http://www.ntt-east.co.jp/mdn/ryokin.html (in Japanese).

Keisuke Ishibashi
received his B.S.
and M.S. in Mathematics from Tohoku
University, Miyagi, Japan in 1993 and1995, respectively. Since joining NTT in
1995, he has been engaged in researchon traﬃc issues in computer communication networks. He received IEICE’s
Young Investigators Award and Information Network research award in 2002.
Mr. Ishibashi is a member of the IEEEand the Operations Research Society ofJapan.

ISHIBASHI et al.: CAPACITY DIMENSIONING OF VPN ACCESS LINKS FOR ELASTIC TRAFFIC IN THE HOSE MODEL141
Mika Ishizuka
graduated from Keio
University, Tokyo, with B.E. and M.E. degrees in Control Engineering in 1992 and1994, respectively. In 1994, she joined
NTT and has been engaged in research on
traﬃc control in computer networks. She
received the IEICE Information Networks
Research Award in 2003. Ms. Ishizuka isa member of the Operations Research Society of Japan.

Masaki Aida
received his B.Sc.
and M.Sc. in Theoretical Physics from
St. Paul’s University, Tokyo, in 1987 and1989, and received his Ph.D. in Telecommunications Engineering from the University of Tokyo, in 1999. Since joining
NTT Laboratories in 1989, he has been
mainly engaged in research on traﬃc issues in ATM networks. From March 1998
to March 2001, he was a manager at theTraﬃc Research Center of NTT Advanced
Technology Corporation (NTT-AT). He is currently a Senior Research Engineer at NTT Information Sharing Platform Laboratories. His current interests include traﬃc issues in communications systems. He received IEICE’s Young Investigators Awardin 1996. Dr. Aida is a member of the IEEE and the Operations
Research Society of Japan.

Shin-ichi Kuribayashi
received
his B.S., M.S., and Ph.D. in Engineering from Tohoku University, Sendai, in
1978, 1980, and 1988 respectively. He
joined NTT Electrical Communications
Labs in 1980. He has been engaged in
the design and development of DDX andISDN packet switching, ATM, PHS, andIMT2000 and IP-VPN systems. He researched distributed communication systems at Stanford University from December 1988 through December 1989. He participated in international standardization on ATM signaling and IMT2000 signaling
protocols at the ITU-T SG11 from 1990 through 2000. He is now
responsible for next-generation IP systems work at NTT Information Sharing Platform Labs.