- 1 -
中国科技论文在线
A grey model based prediction of the popular BGP prefixes
ZHANG Wei*
(National Defense Information Academy, WuHan 430010)
Abstract: Internet core routers are facing challenges brought by the ever-increasing transit bandwidth 5
and routing scale. In order to meet the requirements of highly efficient packet forwarding, some
solutions propose to load a small portion of the BGP RIB entries into the FIB. Therefore the most
popular prefixes, which contribute major traffic loads, need to be cached in the FIB as long as possible.
In this paper, we try to propose a prediction based method to cache those popular prefixes in the FIB.
The cache strategy is guided by the traffic prediction of a grey model. We also apply FIB aggregation 10
techniques to suppress the number of overlapped sub-prefixes of the popular prefixes on cache/route
updates. We evaluate our method with real traffic traces and find that our prediction-based cache
replacement strategy outperforms other cache strategies and matches Internet traffic dynamics very
well.
Keywords: Internet; BGP; Popular Prefix; Route caching; grey model 15
0 Introduction
Internet core routers are facing challenges brought by the ever-increasing transit bandwidth
and routing scale. The Autonomous System border routers (ASBRs) may have to process packets
on each port at a rate of 40 Gbps. This requirement can only be met by applying high-performance 20
hardware, such as TCAM or SRAM. However, this kind of special-purpose memory is costly and
energy eager while normally its size can not be very large. On the other hand, the size of BGP
Route Information Base (RIB) increases inexorably. If we load every entry of the route table into
the Forwarding Information Base (FIB), a router is compellingly under a great pressure of FIB
inflation. 25
Recently there are some new proposals to address this routing scalability problem. Although
there might be different solutions to tackle this problem, the most straightforward method is to
load a small portion of RIB entries into the FIB. This method can be modeled as a route caching
mechanism in a dynamic routing system.
For example, the “virtual aggregation” [1], devices a “distributed forwarding” scheme to 30
reduce the size of FIB. In this scheme, a VA router loads a small portion of RIB into the local FIB.
If the VA router does not have an “exact” route in the FIB for an incoming packet, the packet
needs to be forwarded to a corresponding Virtual Prefix Router (VPR) via tunnels. In order to
improve the routing performance, ViAggre suggests loading most “popular” prefixes into the FIB.
The popularity of a prefix is determined by the hitting rate of working traffic loads on it. In the 35
rest of this paper we continue to use the conception of “popular prefixes” as defined in ViAggre.
Another route caching scenario is with the Openflow [2] application. The Openflow manages
to decouple the forwarding and routing functioning but in a centralized controlling scheme.
Switches or other forwarding devices will be controlled by a concentrated controller which sends
flow tables to Openflow enabled facilities. Since most forwarding devices cannot maintain a large 40
FIB, the routes (defined as flows) stored in the FIB can be dumped as they are “obsolete”. In other
words, the switch boxes cache partial routes of the RIB. Any “unknown” flow (not defined in a
flow table) will be handed to the controller. As a focal point of the routing system, the controller
would become a bottleneck if there are too many packets need to be handled by the controller. In
this case, it would be admirable if the cache mechanism guarantees popular prefixes always stay in 45
Brief author introduction:ZHANG Wei, (1972-),male,lecturer,he received his . degree in computer science
from Tsinghua University, Beijing, China. His research interests include Network Architecture, Internet Routing
and Addressing, IPv6 and Future Internet.
- 2 -
中国科技论文在线
the flow tables of the forwarding boxes.
Motivated by these considerations, we propose to take advantage of the features of the real
traffics, and dynamically cache the popular prefixes based on an effective traffic prediction
method.
The rest of the paper proceeds as follows. In section II, we review related works. In section 50
III, we discuss route caching mechanism and relevant cache strategies. In section IV, we analyze
the feature of Internet traffic and introduce the grey model prediction we use in our method. In
section V, we propose our prediction based cache strategy in detail as well as the solution of prefix
overlapping problem. In section VI, we evaluate our method via simulations on real traffics and
explain our findings. In the end, we draw a conclusion.. 55
1 Related works
ViAggre [1] statically sets a few popular prefixes measured on the routers of an ISP/Point of
Presence (PoP). Their experiments show that loading a relatively static popular prefix set can
improve the performance undoubtedly. However they assume the set of popular prefixes is very
stable and can be set statically. 60
Dynamically updating route cache on routers is not new though [3, 4]. About two decades
ago, many routers had a route caching capability to store frequently used prefixes. But this kind of
hardware cache architecture was overwhelmed by TCAM/SRAM techniques due to the prohibitive
cost of a cache miss. Lately the routing scalability problem urged us to revisit the route cache
mechanism. Changhoon Kim et al. [5] argue that dynamic route caching is still viable because the 65
Internet traffic exhibits high degrees of temporal locality (as packets are grouped into flows, which
are often transmitted in bursts) and spatial locality (as many hosts access a small number of
popular destinations). However, they measured these features only based on a uniform class prefix
(. with a fixed-length of /24). Their evaluation on the Least Recently Used/Least Frequently
Used (LRU/LFU) cache replacement strategies was also based on this uniform granularity of 70
aggregation. Although the uniform class prefix avoids prefix overlapping problem when swapping
routes in/out the FIB, it makes the cache size even bigger than present RIB size. In their
experiment, the routes are non-aggregatable and there are approximately 500k~1M routes to be
stored in the cache for an acceptable route miss rate. The gain of CIDR aggregation is eliminated
in this method. Their research gives no description about the traffic’s locality features on the basis 75
of CIDR prefixes as in BGP route tables.
Another related work in [6] addresses similar route cache functioning but from the
perspective of ID/Locator mapping mechanism designed in ID/Locator split schemes, and
discusses the cost of route caching on the granularity of BGP prefixes1. Their research focuses on
the efficiency of a pull-model-based ID/Locator mapping mechanism. In [6], the cache policy 80
involves a timeout threshold for all cached entries. Each cached prefix has a timer to record the
time since its last “hit”. Once the timer runs over the timeout threshold, the prefix is expired and
dumped. A cache hit will trigger a renewing of its timer and a cache miss would trigger the
loading of this prefix into the cache. Actually the timeout threshold is a tune knob to adjust the
tradeoff between the cache size and the number of “misses”. This cache policy expects some 85
“popular” prefixes repeatedly being “hit” from time to time by the working traffic and therefore
will not be easily dumped. Their evaluation is based on a traffic trace collected on the campus
1 The prefix blocks assigned by RIRs and assumed no overlapping, a simplification taken in this research.
- 3 -
中国科技论文在线
border routers and the result shows the cache size scaled with the traffic loads, which means at
busy hours the required cache can be very large and theoretically no certain boundary.
As a good extension of traffic profiling at the level of single IP “flow” (concerning individual 90
destination IP address), some recent traffic modeling studies [7, 8] pay special attention to the
characteristics of conglomerated traffics over IP prefixes. In [7], the Internet prefix-level traffic
behavior has been investigated and empirically validated the spatial clustering feature of traffics of
a tier-1 ISP. Eddie Kohler et al. in [8] investigate the structure of addresses contained in IP traffic
and explored the multifractality of Internet traffics with different prefix lengths (from the scale of 95
/0 to /32). Their measurements observe the essential dynamics of Internet traffics over a certain
span of address spaces, however, their studies cannot address the interference between the traffic
and real BGP prefixes. This limitation is partly due to the fact that their traffic traces had been
anonymized and could not match the BGP RIB anymore. Furthermore their studies are mainly
focused on general modeling or traffic classification and traffic load over a certain IP prefix is 100
only one of the measuring dimensions.
This paper try to highlight the features of working traffic on dynamics of AS level traffic
loads over real BGP prefixes and apply them to facilitate pragmatic route caching mechanisms.
2 Route caching mechanism and strategies
The route caching mechanism can be abstracted as the following conceptual model: to store a 105
small fraction of the routes in a size-limited but efficient cache, and a full route table will be stored
in a relatively slow but bigger memory and can be accessed with some overheads. A cache “miss”
surely introduces considerable delay or other costs. The objective to optimize the performance of
the cache is to minimize the cache miss rate.
In this model one great challenge is that the popularity of a prefix is dynamically determined 110
by the interfering of two changing elements: the RIB entries and the working traffic loads on it.
We have already known the Internet traffic exhibits locality properties (temporal and spatial) and
the packet traffic is non-uniformly distributed [9,10]. We need to device proper cache replacement
strategies to match the fundamental dynamics of the working traffic over CIDR prefixes.
We will discuss some relevant cache replacement strategies applied in the route caching 115
mechanism before we devise new cache strategy by taking advantage of the features of working
traffics.
Static strategy
This is the most straightforward strategy and it depends on the assumption that most of the
popular prefixes are stable. The cached routes will not be updated for a long period of time. 120
Normally the cached popular prefixes are chosen by hand (based on personal experience or
preference). Any replacement requires administrators’ involvement therefore the administrative
cost can be very high.
Cache-miss-based Dynamic Strategies
For this kind of dynamic strategy, the cache replacement can happen at any time, only 125
triggered by a cache miss. There are different algorithms. Basically LRU and LFU are typical
strategies.
z Least Recently Used (LRU)
LRU, as the name shows, will dump the least recently used prefix out when the cache is full and
new routes have to be cached. This strategy stresses the temporal locality which assumes the least 130
recently used prefix will not likely be needed in the close future.
z Least Frequently Used (LFU)
- 4 -
中国科技论文在线
LFU can be regarded as the counterpart of LRU. LFU will dump the least frequently used prefix
instead, if a new prefix needs to be cached and the cache is full. This strategy stresses spatial locality
which assumes the least frequently used prefix has the lowest probability to be required in the close 135
future.
z Timeout Dump (TD)
This strategy is proposed in [6]. Theoretically the cache size is unbound. The TD maintains a
timer of not being hit for every prefixes in the cache. Once the timer gets over a threshold, the
prefix should be dumped. The number of cached routes scales with the volume of the timeout 140
threshold and the traffic loads. At busy hours, the hitting prefixes may have a great diversity,
which means there probably will be a lot of routes to be cached. Anyway the timeout threshold
can be used to control the cache size in the worst case. Of course one may design a variant TD by
setting a “cache let in” threshold which means a prefix can only be cached when its hitting rate is
higher than the “let in” threshold. Therefore the cache size can be manipulated by these two 145
thresholds.
All above cache-miss-based algorithms are conducted on the packet level, and may require
replacement when a cache miss happens. The overheads of this kind of strategies can be very high
when numerous bursty traffics exist.
Optimal (Opt) 150
The Opt strategy is the theoretical limit as it requires future knowledge. The Opt algorithm
dumps prefixes that will be least needed in the future therefore it has the least cache miss rate.
Note that the Opt can not be implemented in practice and is be used as a theoretical comparison.
All these replacement strategies tend to catch popular prefixes in a route caching mechanism.
Except the static strategy, the others are adaptive to the traffic dynamics. Their efficiencies depend 155
on how good they may fit the property of the traffic load distribution across prefixes. We need to
have a general analysis on these features of the Internet traffic before we can justifiably propose
our purposive contribution.
3 Internet traffic prediction
Internet traffic features 160
Many previous network measurement studies have found that the Internet traffic has a feature
of power law distribution [11, 12, 13, 14] that a few prefixes contribute most traffic loads and the
rest prefixes in the RIB have only trivial or non traffic in a certain time span. This power-law
observation has held up in the past decades and hopefully will hold up in the future. This feature
makes the route caching mechanism viable and beneficial. The power-law distribution of traffic 165
loads over different prefixes means too many prefixes only contribute trivial traffic loads. There
comes our basic understanding that to give up those trivial traffics is a good strategy on
controlling the size of route cache. In this paper we focus on the popular prefixes which contribute
most traffic loads.
More complicated is the dynamics of the popular prefixes. Some studies simply believe the 170
popular prefixes are rather stable [1]. If this assumption always holds to be true, a static cache can
be built and could be a best strategy. However our observation and other experimental research
[10,11] show the popularity of a prefix only has short term stability. The traffic on a prefix can be
very bursty, and a popular prefix can not have heavy traffic loads for all the time. Generally
speaking the popularity of a prefix is most likely instable when observed on short term time scales. 175
However, the dynamics of a traffic load over a span of address space shows a property of
self-similarity. Self-similarity also manifests itself as long-range dependence (or long memory) in
- 5 -
中国科技论文在线
the time series of arrivals. This means that there are non-negligible correlations between the
arrival counts in time intervals that are far apart. We suspect that the traffic on a popular prefix is
not only bursty but has a “memory” at different time scales as well. To retrieve the “memory” 180
from the traffic traces may help us to estimate the traffic loads in the future. Modeling this traffic
property is beyond the realm of this paper. Nevertheless this empirical understanding is very
helpful on designing a practical cache replacement method.
Grey Model for traffic prediction
On predicting the traffic over different prefixes, we apply a grey model [15], which is 185
typically used in grey system control and prediction. This model assumes that although the
elements that influence the traffic loads cannot be depicted with explicit functions, their general
effect has been illustrated in the traffic traces. The traffic load is influenced by a “grey” system
which we may by and large estimate its overall behavior in the next stage if we can effectively
retrieve enough information from the traffic traces. 190
The mathematical analysis of the grey model can be found in [15]. Here we only deliver the
GM(1,1) modeling process in our specific prediction application.
On applying GM(1,1) model, we should calculate the traffic loads of each prefix within every
time of intervals. Then we have a series of traffic loads for each prefix in the RIB as )(
0 tX ,
where t=0,1,2…; after an accumulation generation operation(AGO), we have )(
1 tX , the 195
cumulative series of )(
0 tX , and formally
∑
=
=
t
i
iXtX
0
01 )()( , t=0,1,2,…
The GM(1,1) model mathematically assumes the cumulative series is continuous and abides
with the following difference equation:
utaX
dt
tdX =+ )()( 1
1
(1) 200
After Laplace transform and inverse Laplace transform, we have the solution of the
differential equation:
a
ue
a
uXtX at +−=+ −))1(()1( 01 (2)
In equation (1) and (2), a and u are parameters which can be estimated through least square
method. 205
YBBBuaA TTT 1)()ˆ,ˆ(ˆ −== (3)
where
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
−+−
+−
+−
=
1
...
1
1
))1()((
...
))2()3((
))1()2((
11
11
11
txtx
xx
xx
B
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
−
=
)(
...
)3(
)2(
0
0
0
tx
x
x
Y
After that, we substitute aˆ and uˆ into equation (2), and then inverse the AGO operation. 210
- 6 -
中国科技论文在线
The prediction of the traffic load will be
)(ˆ)1(ˆ)1(ˆ 110 tXtXtX −+=+ .
This model treats the accumulative traffic load as the single variable that its current variance
is only subjected to its previous amount. This model establishes a first order differential equation
shown in (1). The GM(1,1) model, namely a single variable )(
1 tX and its first order differential 215
equation, has been widely used in grey prediction applications.
Technically, if )(
1 tX is high, we hope its variance accordingly low, which means a stable
popular prefix ( )(
1 tX has a high volume with low variance) matches the model better than
otherwise. Those prefixes that do not match the model may have morbid parameters after
regression. Here we define a forbidden area for parameter a. Once the estimated parameter a falls 220
into a forbidden area: ),2[]2,( ∞−−∞ U , the prefix is not predictable and cannot be a candidate
stable popular prefix. In this case, the traffic over such a prefix is random. We believe there is no
general trend that could be extracted from its traffic trace. In our algorithm, we only accept the
prediction with )2,2(−∈a , since predict the unpredictable prefixes are meaningless. This method
can extract useful information from a grey system efficiently. 225
The grey model has the following virtues. Firstly, the accumulative series depicts a general
trend of the traffic with certain degree of confidence which is essential to our traffic prediction.
Secondly, it is adaptive to burstness of the traffic loads over prefixes. If we estimate the popularity
of a prefix by simply calculating an averaged traffic load over a period of time, the traffic burst of
a non-popular prefix may influence our judgment especially when the traffic trace is insufficiently 230
informative. Thirdly, the irrelevant prefixes can be differentiated easily (if the parameter a falls
into the forbidden area). Lastly, the grey model requires not too much input information compared
with other models. It is very suitable to the situation of sketchy forecasting.
4 Prediction based route caching strategy
Based on the GM(1,1) traffic prediction, our route caching strategy will dump non-popular 235
routes out and load potential popular prefixes periodically.
In our scheme, we need a few sampled traffic traces to guide our prediction. Instead of
triggering a cache replacement by a cache “miss”, we can estimate the popular prefixes of the next
stage beforehand. The cache loading/dumping is solely based on this “prediction” and takes place
with a certain intervals. The size of the cache and the intervals of the cache replacement may vary 240
according to the hardware capacity.
In our strategy, at first we need to set a replacement interval (such as 5 minutes, 1 hour or
even longer). This setting is a tradeoff between performance and overhead. A shorter interval
may have higher cache efficiency but also introduces more computational overheads.
In order to reduce the overheads of frequent cache/route replacement, we suggest using two 245
independent memories for forwarding lookups. And the forwarding lookups will be carried on in
turns with these two memories. When one memory is used as a working cache, the other is used
for loading the caching routes on the next stage. As soon as the replacement happens the
forwarding lookups will be switched to the alternate memory. This mechanism guarantees there
will be almost no delay of cache replacement which is extremely important for high speed routers. 250
In the case of route updates, the FIB loading can be triggered immediately without waiting
for the next due time of a cache replacement. There is a copy of the current route cache in the
FIB calculating device therefore any route update that involves the current cached routes can be
recalculated immediately and update the cache without too much delay. After loading the updated
- 7 -
中国科技论文在线
cache, the standby memory can be activated as the working cache which means a cache memory 255
switch has been triggered by route updates.
Another issue that needs to be taken into consideration is the problem of loading overlapped
prefixes. In order to guarantee correct forwarding with longest prefix match algorithm, when we
load a less specific prefix as popular prefix, all its more specific covered prefixes (sub-prefixes)
have to be loaded as well. Otherwise there will be a routing problem. These overlapped prefixes 260
make the cache size bigger than the popular prefix set that we estimate. Basically the size of the
popular prefix set is proportional to the final cache size. Sometimes a prefix may have as many as
more than 2000 sub-prefixes. In this case we adapt a FIB suppressing algorithm, Optimal Route
Table Constructor (ORTC) [16], to reduce the number of sub-prefixes and consequently to reduce
the ratio of the cache size and the accommodated popular prefix set. 265
In our scheme, we only apply ORTC FIB compressing when a popular prefix has
sub-prefixes in the RIB. We set the popular prefix as the root of the ORTC tree. It has been proven
in [16] that ORTC is the optimal FIB suppressing algorithm. The gain of ORTC depends on the
number of forwarding next hops and the forwarding redundancy of routes. Our simulation shows
that ORTC can effectively reduce the number of sub-prefixes for all popular prefixes. 270
The only limitation of ORTC is the problem of route update. Because the next hop of a prefix
may be different with the corresponding entry in the RIB and even new prefixes can be generated,
each route update requires recalculation of the entire tree. The incremental route update is not
possible in this case. However, in our scheme the recalculation will be limited to relevant popular
prefixes. Moreover a standby memory is always ready for route updates and popular prefix swaps. 275
Generally the overheads of ORTC recalculation and route updates are acceptable.
The overall implementation of our scheme can be illustrated in a conceptual router model as
shown in Figure 1.
In use Cache Memory
Standby Cache Memory
Input traffic
forwarding lookup requests
Traffic collection
RIB
Traffic statistics Popular prefix prediction
FIB (partial routes of RIB)
FIB Loading
FIB Suppression
Route update
ORTC recalculation on
RIB update
Image of Cache in use
BGP update
ORTC
Forwarding actions
(responses)
In use Cache Memory
Standby Cache Memory
Input traffic
forwarding lookup requests
Traffic collection
RIB
Traffic statistics Popular prefix prediction
FIB (partial routes of RIB)
FIB Loading
FIB Suppression
Route update
ORTC recalculation on
RIB update
Image of Cache in use
BGP update
ORTC
Forwarding actions
(responses)
A prediction based route cache mechanism in a router model 280
We evaluated our method with the working traffic traces collected from the China Telecom
backbone networks and our campus networks gateway accessed to the CERNET.
5 Evaluation
Methodology 285
We collected traffic trace and corresponding route tables provided by CHINANET [17], the
backbone of China Telecom. In addition to the traffic trace collected from large ISP, we also collected
traffic data on the gateway of our campus networks which accesses the Internet via CERNET. As
complementary data to the major ISPs, the traffic in the CERNET networks can represent most stub
ASes at the edge of the Internet. However, our analysis will focus on the dataset collected from 290
- 8 -
中国科技论文在线
CHINANET, and the campus traffic has the similar outcome in our simulation.
We collected sampled flow-level Netflow traces in a period of two months (from 14th Nov
2009 to 16th Jan 2010) at different backbone routers located on two PoPs of CHINANET. In
CHINANET, China Telecom IP network services are delivered over the international 40Gbps
MPLS-enabled IP backbone. Since the volume of the traffic transited by those routers was 295
extremely large, the Netflow sampling rate was set as 1:5000 with the sampling techniques
specified in [18]. Basically our experiments were based on this sampling rate.
We used selected traffic traces from two routers in Shanghai and Guangzhou respectively to
generate per-prefix traffic statistics. We observed that a small fraction of Internet prefixes carried
a large majority of ISP traffic. This observation was also found in previous studies [1,14,19,20,21]. 300
Our measurements confirmed this property which is the prerequisite of route caching.
Then we measured the dynamics of popular prefixes by means of variance analysis. We
found the dynamics of popular prefix can be commonly featured at all AS border routers.
At last we evaluated different cache replacement strategies over working traffic traces (from
14th to 16th of Jan 2010). A reasonable range of reference history against different sizes of caches 305
had also been measured. Basically our interests focused on the tradeoff among cache size, route
miss rate and corresponding overheads.
Observations
Figure 2 shows our observation of the traffic distribution across BGP prefixes on 14th JAN
2010. Of all the 336390 prefixes we calculate the number of packets hitting on each prefixes. Our 310
observation is that 143950 prefixes (account for % of RIB) had no traffic at all that day. And
when we sort the rest prefixes by their daily traffic loads and plot it in a “log-log” format, we get a
linear track which is typically a Zipf distribution. It can be seen clearer in a CDF format of the
traffic distribution over all prefixes, as shown in Figure 3. We find that 95% traffic is contributed
by no more than 5% BGP prefixes. But the popularity of each individual prefix is not stable in a 315
large time scale.
In order to illustrate the dynamics of the variable popularity, we calculate the traffic on a
smaller time scale (at an interval of 5 minutes). That is to say we count the packets on each
prefixes for every 5 minutes in a day, and consequently we have a discrete series x representing
the traffic loads at 288 discrete time slots of a day for each prefix. In this N288 matrix (N is the 320
number of RIB entries), we find the traffic loads on a given prefix at successive time slots may
change drastically from time to time which is the burstness observed as a common understanding.
On observing the stability coupled with its popularity of a prefix, we calculate the mean value
and variance of x. Then we give a generalized metric to measure the popularity and stability of a
prefix simultaneously: the ratio R between averaged traffic loads and variance of x, as shown in 325
formula (4).
otherwise
xVarifxVarxMean
R
0)(
0
)()( ≠
⎩⎨
⎧= (4)
In which,
;288)(
288
1
∑
=
=
i
ixxMean
2
288
1
))(()( ∑
=
−=
i
i xMeanxxVar 330
- 9 -
中国科技论文在线
A Zipf distribution of the Internet traffic loads over each BGP prefixes as plotted in a log-log style.
75
80
85
90
95
100
1 2 3 4 5 6 7 8 9 10
% of most popular RIB prefixes
%
of
t
ra
ff
ic
l
oa
d
co
nt
ri
bu
ti
on
s
Fig. 3 CDF of contributed traffic load over most popular prefixes on the 14th Jan 2010 at a CHINANET core 335
router.
Obviously, a stable popular prefix will have substantially high traffic loads and relatively low
variance, and its value of R generally should be higher than otherwise. We plot the R value of each
prefixes in figure 4, and find that a small portion (2~3% of RIB size) of prefixes can be both 340
“popular” and relatively stable (from point A to B) all day long. These prefixes are rather stable
and contribute major traffic loads and should be kept in the cache as long as possible. Although
not confirmed, we suspect this portion of stable popular prefixes is the popular prefix set measured
in [1] which accounts for 2% of the RIB. Other relatively instable popular prefixes (from point B
to C) have changing popularities but still contribute considerable traffic loads. As the variance 345
increasing, the value of R will decrease accordingly. We see in Figure 4 from point B to C a
declining track which implies the increasing instability of such popular prefixes or a declining of
contribution to traffic loads. These prefixes can only be caught effectively by dynamic cache
strategies. Our prediction based method can differentiate them from normal traffic bursts. Beyond
point C are non-popular prefixes. Remember among 336390 prefixes being measured, almost half 350
of them have extremely trivial traffic for all 288 time slots in a day. The above observation
illustrates the fact that in BGP RIB, we have stable popular prefixes, instable popular prefixes and
non popular prefixes. Assuming the popularity of any prefix is stable and only adapt static strategy
could be too ideal and far from optimal.
- 10 -
中国科技论文在线
355
Figure 4: Traffic dynamics over prefixes
0
0 10000 20000 30000 40000 50000 60000
Number of Popular Prefixes
%
of
c
ac
he
m
is
s
tr
af
fi
c
Replacement interval of 5 min
Replacement interval of 1 hour
Replacement interval of 1 day
Figure 5: Comparison of different cache replacement intervals with corresponding theoretical limits.
On analyzing the dynamic strategies of route caching mechanism, we first apply optimal 360
strategy as a background to show the theoretical limits at different cache size and replacement
frequencies. This strategy can preload popular prefixes exactly accurate since it had the future
knowledge. These theoretical limits can be different since it uniquely depends on the features of
the traffic.
On plotting the limits of different replacement frequencies and cache sizes in figure 5 we can 365
get some basic understandings of the Internet traffics. Firstly, at a given cache miss rate and
replacement interval, we can estimate the least cache size which is the vital parameter in our
method. Secondly, as we can see in Figure 5, there is a diminishing marginal utility of caching
more prefixes: soon after the size of the cache exceeded 5%of the RIB size (about 18000 entries),
the miss rate decreases slowly with the increasing size. After loading 10% of the RIB (33000 370
prefixes) as popular prefixes, the miss rate decreases rather slow and almost has no obvious gains
if the replacement takes place frequently. This fact implies that numerous prefixes contribute
trivial traffic loads and suggests an efficient cache size will be around the turning points. Based on
this observation we can tune a better tradeoff between the cache size, cache miss rate and cache
update intervals (overheads). Our method attempts to find a proper point within the tradeoff 375
triangle.
- 11 -
中国科技论文在线
Performance Evaluation
On evaluating the performance of our method, we simulated different strategies as a
comparison. We plot in Figure 6 the performances of static cache strategy, cache-miss-based
strategy (LRU) and prediction-based strategy respectively. 380
%
%
%
%
%
%
%
%
%
0 10000 20000 30000 40000 50000 60000
Number of Popular Prefixes
%
of
C
ac
he
M
is
s
Tr
af
fi
c
Optimal(theoratical limit)
Static Strategy
Cache-Miss-Based Cache Update(LRU)
prediction-based cache update/5min
Prediction-based cache update/hour
Prediction-based cache update/day
Figure 6: Comparison of different strategies.
Static cache has the highest miss rate. The popular prefixes set we used in static method was
measured on a given day with the optimal strategy at the same router. In static strategy, we assume 385
the most popular prefixes that day (account for approximately 2% of RIB) are in the cache and
will not be replaced for a long time, but the other prefixes in the cache are randomly chosen if the
cache size is more than 2% of RIB. To some extent, the static strategy can be viewed as the
extreme situation where we set the replacement interval as infinity. In this way, we have long-term
stable popular prefixes in the cache, but they are not necessarily stable on smaller time scales. 390
Since there are only very few popular prefixes have short-term stability, most short-term instable
popular prefixes can only be caught effectively by dynamic cache strategies. However, when the
caches size is extremely small, it performs even better than that of LRU. In most cases, the cache
size is not so constraint, and static method gains less than the other dynamic cache strategies.
Cache-miss-based strategies (such as LRU/LFU) can catch the instable popular prefixes, but 395
some bursty traffic will influence the route caching efficiency from time to time and might incur
much higher overheads when replace cache items on each cache miss.
Since we do not have a packet-level trace, we simulate LRU strategy based on our flow-level
Netflow traces. In the Netflow records, the start time and end time of a flow could be marked as
the arriving time of the first and last packet. We further simulate the arriving time of the rest 400
packets randomly between the start time and end time of the flow. In the study of [6], their
experiments proved that LRU had better performance than LFU, so we choose LRU to evaluate
the cache-miss-based strategy. Our experiment shows LRU is not as good as the static strategy if
the cache size is fairly small and generally no better than our method at all cache sizes.
- 12 -
中国科技论文在线
Set 3% of the RIB as popular prefixes
%
%
%
%
%
%
%
%
0 50 100 150 200
Range of referring history (min)
Pe
rc
en
ta
ge
o
f
ca
ch
e
mi
ss
ed
t
ra
ff
ic cache replacement/5min
cache replacement/hour
405
Figure 7: Reasonable range of reference for a valid prediction
Our prediction based method will replace the cached prefixes periodically with determined
intervals. It can catch most of the popular prefixes solely guided by traffic traces. It is almost
immune to the traffic bursts if we set a proper range of reference traffic traces. Figure 7 illustrates 410
the ideal range of reference is about 50 minutes when we set the cache size as 3% of the RIB.
%
%
%
%
%
%
%
%
%
%
0 10000 20000 30000 40000 50000 60000 70000
Number of Prefixes
%
of
T
ra
ff
ic
C
on
tr
ib
ut
io
n
Sheer set of popular prefixes without
overlapped sub-prefixes
Popular prefixes with their covered sub-
prefixes
Aftre ORTC suppression
Figure 8: Comparison of caching popular prefixes with and without their covered non-popular sub-prefixes, as well
as the FIB suppression effects of ORTC. 415
The last important measurement of our study is the overlapped sub-prefixes of the popular
prefixes. As plotted in Figure 8, without ORTC, in the worst cases, the cache size can be almost 5
times as big as the sheer popular prefix set, which means we have to load many non-popular
sub-prefixes into the cache. With ORTC, the number of sub-prefixes reduces considerably and the 420
overall cache size is about a double size of the sheer popular prefix set which is affordable when
the popular prefix set is only 2~5% of the RIB. Hopefully we can reduce the requirement of the
FIB size an order of magnitude with no more than 5% cache miss rate.
On evaluating the overheads of our method, the traffic trace collection requires about 10MB
in a relatively slow memory, the prediction process will take no more than 30 seconds and FIB 425
suppression algorithm will take no more than 40 seconds. The standby cache memory will be
ready on time for cache replacement. The route update only involves the updated popular routes.
An ORTC recalculation of the updated popular prefix is optional but it surely will have no
significant delay because the other cached routes will not change.
With the experiments on the working Internet traffics, our method can dynamically cache 430
5~10% of BGP RIB with 2 independent caches, the cache miss rate is less than 5%; the ideal
- 13 -
中国科技论文在线
cache replacement interval is 5 minutes and a less frequent replacement strategy may introduce
corresponding higher miss rate(there always exists a tradeoff between performance and overhead);
the reasonable range of reference traffic trace is no more than one hour; the sampling statistic of
the traffic loads can be optional and the sampling ratio can be adjusted according to the general 435
traffic load on the router. The GM(1,1) prediction is not very much sensitive to the sampling ratio.
6 Conclusion
Our study gives an in depth research on the features of the Internet traffic distribution across
BGP prefixes. The popularity of a prefix may be instable. On the other hand the BGP prefixes are
heavily overlapped with each other. These two facts introduce two major challenges on the route 440
caching mechanism: how to catch the instable popular prefixes efficiently and ameliorate the side
effect of loading their non-popular sub-prefixes effectively.
Our method addresses these two problems by apply a grey model prediction and the FIB
aggression technique. The GM(1,1) model can retrieve information efficiently from limited traffic
traces and adaptive to the bursts over non-popular prefixes very well. The ORTC algorithm can 445
suppress the number of sub-prefixes effectively when loading a popular prefix into the cache.
On empirically analyzing the dynamics of popular prefixes in the working traffics, we
evaluate our prediction based route caching strategy that matches the Internet traffic at AS border
routers better than other cache strategies. The simulations have shown that the general overheads
of our method are acceptable and the performance is close to the ideal limits. 450
Acknowledgements
This work was supported by National Science Foundation of China under Grant 61073172,
Program for New Century Excellent Talents in University, Specialized Research Fund for the
Doctoral Program of Higher Education of China under Grant 200800030034, and National Basic
Research Program ("973" Program) of China under Grant 2009CB320501. 455
References
[1] H. Ballani, P. Francis, T. Cao, J. Wang, Making Routers Last Longer with ViAggre[A], Proceedings of
USENIX NSDI '09[C], 2009.
[2] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, 460
OpenFlow: Enabling Innovation in Campus Networks[OL], [2008]
.
[3] How to Choose the Best Router Switching Path for Your Network. Cisco Systems[OL].
[2005].
[4] C. Partridge, P. Carvey, A 50-Gb/s IP router[J], IEEE/ACM Transactions on Networking, 1998 6(3): 237-248. 465
[5] C. Kim, M. Caesar, A. Gerber, and J. Rexford, Revisiting Route Caching: The World Should Be Flat[A],
Proceedings of PAM '09[C], 2009.
[6] L. Iannone, O. Bonaventure, On the Cost of Caching Locator/ID Mappings[A], proceedings of CoNEXT '07[C],
2007.
[7] H. Jiang, Z. Ge, S. Jin, J. Wang, Network prefix-level traffic profiling: Characterizing, modeling, and 470
evalution[A], Computer Networks, 2010,54(18): 3327-3340.
[8] E. Kohler, J. Li, V. Paxson, S. Shenker, Observed structure of addresses in IP traffic[J], Transactions on
Networks, 2006,14 (6): 1207-1218.
[9] C. Park ,. Campos, . Marron, . Smith, Long-range dependence in a changing Internet traffic mix[J],
Computer Networks, 2005, 48(3): 401-422. 475
[10] C. Williamson, Internet Traffic Measurement[J], IEEE Internet Computing, 2001, 5(6): 70-74.
[11] M. Arlitt, C. Williamson, Internet Web Servers: Workload Characterization and Performance Implications[J],
IEEE/ACM Transactions on Networking, 1997, 5(5): 815-826.
[12] L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker, Web Caching and Zipf-like Distributions: Evidence and
Implications[A], Proceedings of IEEE INFOCOM '99[C], 1999. 480
[13] M. Crovella, A. Bestavros, Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes[J],
IEEE/ACM Transactions on Networking, 1997,5(6): 835-846.
- 14 -
中国科技论文在线
[14] W. FANG, L. PETERSON, Inter-As traffic patterns and their implications[A]. Proceedings of Global Internet
'99[C], 1999.
[15] J. Deng, Control problems of grey systems[J], systems & control letters, 1982,1(5): 288-294. 485
[16] . Draves, C. King, S. Venkatachary, . Zill, Constructing Optimal IP routing tables[A], Proceedings of
IEEE INFOCOM '99[C], 1999.
[17] CHINANET[OL].://
[18] Sampled NetFlow[R], Cisco Systems,2010. feature/guide
/. 490
[19] A. FELDMANN, A. GREENBERG, C. LUND, N. REINGOLD, J. REXFORD, F. TRUE, Deriving traffic
demands for operational IP networks: methodology and experience[J], IEEE/ACM Transactions on Networks,
2001,9(3): 265-279.
[20] N. TAFT, S. BHATTACHARYYA, J. JETCHEVA, C. DIOT, Understanding traffic dynamics at a backbone
PoP[A], Proceedings of Scalability and Traffic Control and IP Networks SPIE ITCOM[C], 2001. 495
[21] J. REXFORD, J. WANG, Z. XIAO, Y. ZHANG, BGP routing stability of popular destinations[A],
Proceedings of Internet Measurement Workshop 2002[C], 2002.
基于灰模型的 BGP 热前缀预测
张威 500
（中国人民解放军国防信息学院，武汉 430010）
摘要：英特网核心路由器正面临持续增长的带宽和路由规模的双重挑战。为了满足高性能分
组转发的需求，许多路由解决方案选择仅装载部分路由表项（RIB）到转发表（FIB）中。
这时，FIB 需要装载 RIB 表项中流量贡献最大的热前缀，并使它们缓存的时间尽可能长。本
文应用基于灰模型的流量预测技术，提出了一种基于流量预测的方法用于抓住 BGP 路由表505
中的热前缀。本文还应用了 FIB 聚合技术压缩了路由更新时相互覆盖的 BGP 前缀的数量。
通过真实互联网域间流量对该方法的评估，我们发现基于预测的路由缓存策略优于其它缓存
更新策略，能更好地适合互联网流量的动态特性。
关键词：互联网；BGP；热前缀；路由缓存；灰模型
中图分类号：TP301 510
