Transcript In-Network storage, caching analysis

Challenges in the Design and Evaluation
of Content-Centric Networks
Jim Kurose
Department of Computer Science
University of Massachusetts
Amherst MA USA
‘
Visiting Scientist, Technicolor Paris Lab
Professeur Invite, LINCS
Sigcomm ICN Workshop, Aug 2013
Overview
architecture, system, prototype
 networks of caches

 challenges
 approximation algorithms
 network calculus for cache networks

workload: logical mobility among networks
*
Architecture, System, Prototype
architecture
high-level design/structuring principles, service/function
modularity
guides, informs, inspires, constrains
system
instantiated set of interoperating protocols, mechanisms,
platforms conforming to design principles
“here’s what it does (function), you
tell me how”
prototype
(realization)
Implemented (sub)set of protocols, platforms in particular
existing technologies
* ack: D. Clark, J. Wroclawksi
Architecture, System, Prototype
architecture
system
Minimalist – principles, modularities
Maximalist – protocols,
mechanisms go here
prototype
Architecture, System, Prototype
telephony
architecture
Internet
ICN
end-end circuit,
stateless endpoints,
stateful core, QoS,
single service
datagram, stateful
endpoints, best-effort
stateless core,
multiple services, IP
content,
naming, stateful
core, caching
system
SS7, ESS, MSC,
VLR, HLD
TCP, UDP, DNS,
BGP, IS-IS, OSPF
Ongoing
prototype
many .. over the
years
many .. over the
years
Ramping up …
(routing, congestion
control, caching,
name resolution,
search,…)
Architecture, System, Prototype
telephony
architecture
Internet
ICN
end-end circuit,
stateless endpoints,
stateful core, QoS,
single service
datagram, stateful
endpoints, best-effort
stateless core,
multiple services, IP
content, stateful
core, caching
system
SS7, ESS, MSC,
VLR, HLD
TCP, UDP, DNS,
BGP, IS-IS, OSPF
Ongoing
prototype
many .. over the
years
many .. over the
years
Ramping up …
(routing, congestion
control, caching,
name resolution,
search,…)
Architecture, System, Prototype
Internet
ICN
architecture
content,
stateful
datagram, more
stateful difficult,
Architecture research/evaluation
more
endpoints, best-effort
“fundamental” (?), more impactful
(?)
stateless core,
core, caching
multiple services, IP
system
TCP, UDP, DNS,
BGP, IS-IS, OSPF
Ongoing
(routing, congestion
control, caching,
name resolution,
search,…)
Research/evaluation mostly here: mechanism, protocols
prototype
Architecture, System, Prototype
telephony
architecture
system
Evaluation
Internet
ICN
end-end circuit,
stateful
Kleinrock datagram,
64
stateless endpoints, endpoints,
Cerf, Kahnbest-effort
74
stateful core, QoS, stateless
core,
Clark 1988
single service
multiple
services
McCanne
1998
content, stateful
?
core, caching
SS7, ESS, MSC,
VLR, HLD
Ongoing
Blocking
networks
TCP, UDP, DNS,
BGP, IS-IS, OSPF
Queueing networks
Delay calculus
Effective bandwidths
TCP, NUM optimization
(routing, congestion
control, caching,
name resolution,
search,…)
?
?
Challenges

ICN: architecture vs protocol/mechanism
 elucidation, value-proposition of design principles,
service/function modularities

evaluation tool: networks of caches
Interlude ….
Overview
architecture, system, prototype
 networks of caches

 challenges
 approximation algorithms
 network calculus for cache networks

workload: logical mobility among networks
Cache networks





consumer requests content
request routed (e.g., shortest
path) to known content
content
custodian
custodian
en-route to custodian, caches
inspect request
 hit: return local copy
 miss: forward request
miss
towards custodian
during content download,
store in caches along path
content requests from different users
interact: cache replacement
content
custodian
content
miss
miss
miss
miss
miss
miss
request
Challenge: networks of caches

network effect: interaction among content
request/reply flows from different users:

content replacement: requested content by one user
replaces content previously requested by others
x
Circuit-switching:
blocking networks
(Erlang, 1917, Kelly 1986)
Packet-switching:
queueing networks
(Kleinrock, 1963)
Content-caching:
cache networks
Modeling a network of caches
j
node i: exogenous (external)
arrivals for content j: l(i,j)
 node i: internal arrivals (miss
stream) for content j from
downstream neighbors h:
m(j,h)
 r(i,j): aggregate rate of arrival
requests at i for content j
r(i,j) = l(i,j) +
m(j,h)

S
content
y
i
w
m(j,w)
all downstream
neighbors, h

ZDD: zero download delay
assumption
m(j,i)
m(j,x)
x
l(i,j)
Modeling a network of caches

SCA: standalone cache i approximation algorithm: given
r(i,j), compute miss rate for all content j
Independence Reference Model (IRM) of incoming
requests:
Pr(Xt = fj | X1,..,Xt-1) = Pr(Xt=fi)

SCA approximation algorithm for LRU: [Dan 1985]

r(i,1)
m(i,1)
r(i,n)
m(i,n)
cache i
But we need {(ri,j, mi,j)} for a network of caches
Fixed-point iteration
Using
SCA algorithm
Set r(i,j)=λ(i,j)
Using SCA
algorithm
Compute miss
rate m(i,j)
Compute arrival
rate r(i,j)
Using Routing Matrix 
Repeat until
convergence
Return r(i,j), m(i,j)
Note: tree-network (feed-forward) require single iteration
15
a-NET: approximation error
1.14
line topology with
9 nodes
 errors decrease in
networks with
high node degree

Quality of a-NET
Sim / Approx Misses
1.12
1.10
1.08
1.06
1.04
1.02
1.0
0.98
0
1
2
3
4
5
Cache ID
6
7
8
9
a-NET: error factor analysis
sources of approximation errors in a-NET?
 SCA algorithm inaccuracies
 cascading errors
 approximated output rates of one iteration is input to
next iteration
 violating IRM assumed by SCA algorithm
 miss process for file j negatively correlated
a-NET: error factor analysis
1.14
Quality of a-NET
Cascade Err. removed
Non-IRM removed
Quality of SCA
1.12
Sim / Approx Misses
• Factor analysis
reveals that nonIRM input to SCA
is main cause of
error
1.10
1.08
1.06
1.04
1.02
1.0
0.98
0
1
2
3
4
5
Cache ID
“Approximate Models for General Cache Networks,”
Elisha J. Rosensweig, Jim Kurose, Don Towsley, 2010 IEEE INFOCOM
6
7
8
9
Overview
• architecture, system, prototype
• networks of caches
– challenges
– approximation algorithms
– network calculus for cache networks
• workload: logical mobility among networks
(σi,ρi) analyses of cache networks
(σi,ρi) bounds # requests for fi over [t1,t2]:
t2
 r (t)dt
i
  i ( t 2  t1 )   i
t1
where ri(t) = request rate for fi at time t
Goal: a network calculus for cache networks:
(σ1out,ρ1out)
(σ1in,ρ1in)
f1 requests
fnrequests
t1
(σnin,ρnin)
t0
t1
t0
(σnout,ρnout)
(σi,ρi) cache networks: observations

not all requests arriving at cache will leave (unlike queue)
f1 requests
f2 requests

t1
t0
t1
t0
stream of input requests for one file only generates no
output
 interactions among files in cache critical

“burst” of request for same file generates one output
 different intuition (from queues) about “performance damage” of
bursts
Building block: miss set, Mi
miss set for fi: set of requests for c unique files, other than i
x1 requests for f1
...
...
xn requests for fn
c: cache size
w
Mi(x1, …., xn,c): max number miss sets for file fi, given {xiin}
arrivals, cache of size c.
properties:
 Mi = min(xiin, M)
!!
 xiout < Mi, and this bound is achievable
From (σiin,ρiin) to (σiout,ρiout):
(σiin,ρiin)
(σiout,ρiout)
(σjin,ρjin)
(σjout,ρjout)
fi requests
...
...
fj requests
Theorem: If {(σiin,ρiin)}ni=1 and {(σ’iin,ρ’iin) }ni=1 are globally
tight and ρiin = ρ’iin for all i
then ρiout = ρ’iout
iout independent of {σiin}
From (σiin,ρiin) to (σiout,ρiout):
(σiin,ρiin)
(σiout,ρiout)
(σjin,ρjin)
(σjout,ρjout)
fi requests
...
...
fj requests
Theorem: For a cache of size c:
ρiout = min(ρiin, Mi(ρ1in, … , ρnin,c ))
Can calculate ρiout from {ρiin}
Can compute
iout as well
Numerical example
f0,f
f1,f
2
3
cache size = 2 at each node
homogeneous IRM arrivals, exponential interarrival times
4 files, uniform popularity distribution
miss rate for f3
Numerical example: bounding
results
bound
simulation
Cache ID
Challenges

ICN: architecture vs protocol/mechanism
 elucidation, value-proposition of design principles,
service/function modularities

modeling networks of caches: develop analytic
models for cache networks (ICN)
 equivalent of blocking networks (circuit-switched), or
queueing networks (packet switched)?
 exact in asymptotic regimes?
 ergodicty?
Overview
architecture, system, prototype
 networks of caches

 challenges
 approximation algorithms
 network calculus for cache networks

workload: logical mobility among networks
Characterizing mobility among networks
 Historic shift from PC’s to mobile/embedded devices
• ~5B cell phones (`1B smart) vs. ~1B Internet-connected PC’s
• Mobile data growing exponentially, surpassing wired user
traffic by 2012 [Cisco]
 any evaluation/model (ICN or otherwise) must consider
mobility
 “not your father’s mobility:” characterize mobility
among networks
• distinctly different from physical mobility, models
• physically mobile users may be stationary (from network
transition POV); stationary users may move among networks
(multi-homing, multiple devices)
Characterizing mobility among networks
 Measure mobility among networks via IMAP logs
• online users periodically “push” (background login, check)
email, and/or intentionally read mail
- e.g., [email protected] generated 7,482 IMAP entries 4/14/13 –
6/4/13
• track network location from which IMAP accessed
• 70 users, 4/14/13 – 7/5/13, resident in 183 unique AS
numbers
Where do users (in aggregate) spend time?
Work: 5 college
Mobile: Verizon, AT&T, sprint)
Home: Comcast, Verizon, Verizon, Hughes
Misc: 172 other networks in trace
Users spend most of their time in small number of networks
Where do users (individually) spend time?
Users individually spend most of their time in small number of networks
Multihoming
VERIZON
COMCAST
Multi-homing
Q: How often are users multi-homed?
• 15-min subinterval has IMAP access from two different AS’s
Characterizing mobility among networks
 other characterizations of mobility among networks
 generative mobility-among-network model:
parsimonious Markov chain model for individual user
transitioning among networks
Challenges
 ICN: architecture vs protocol/mechanism
• elucidation, value-proposition of design principles,
service/function modularities
 modeling networks of caches: develop analytic models for
cache networks (ICN)
• equivalent of blocking networks (circuit-switched), or queueing
networks (packet switched)
• exact in asymptotic regimes?
• ergodicty
 traffic models (for ICM and otherwise), with mobile users,
content
• mobility the norm
Conclusion
 architecture, system, prototype
 networks of caches
• challenges
• approximation algorithms
• network calculus for cache networks
 workload: logical mobility among networks
End
?? || /* */
Interesting reading
• J. Wroclawski, “All hat no answers: Some issues related to the
evaluation of architecture,” March 2013 NSF FIA meeting, Salt Lake
City UT
• D. Clark, “The Design Philosophy of the DARPA Internet Protocols,”
ACM Sigcomm 1988, Revised with extensive commentary 2013
• E. Rosensweig, D. Menasche, J. Kurose, “On the Steady-State of
Cache Networks,” IEEE Infocom 2013.
• E. Rosensweig, J. Kurose, “A Network Calculus for Cache Networks,”
IEEE Infocom Mini-conference 2013.
• E. Rosensweig, J. Kurose, D. Towsley, “Approximate Models for
General Cache Networks,” 2010 IEEE Infocom, pp. 1100-1108
• S. Yang, S. Heimlicher, J/.Kurose, A. Venkataramani, “User
Transitioning Among Networks - a Measurement and Modeling
Study”, submitted, 2014.
Ergodicity of cache networks
 does steady state performance
depend on initial conditions
(ergodicity)?
 shown existence of nonergodic cases (replacement
policy, topology, cache size)
 derived sufficient conditions
for ergodicity
 topology (singlecustodian trees)
 from individual ergodicity
to system ergodicity
Requests Requests
for B
for A
A
A
B
B
A
B
Ergodicity of cache networks
 ergodicty (continued):
 showed random
replacement: ergodic
 defined class of nonprotective policies (including
LRU): all ergodic
content