ARTHUR HENRIQUE COUTINHO
ESTRATÉGIAS DE CACHE INTERNO A REDES
CENTRADA EM CONTEÚDO
LONDRINA–PR
2015
ARTHUR HENRIQUE COUTINHO
ESTRATÉGIAS DE CACHE INTERNO A REDES
CENTRADA EM CONTEÚDO
Trabalho de Conclusão de Curso apresentado
ao curso de Bacharelado em Ciência da Computação da Universidade Estadual de Londrina para obtenção do título de Bacharel em
Ciência da Computação.
Orientador: Prof. Dr. Bruno Bogaz Zarpelão
LONDRINA–PR
2015
Arthur Henrique Coutinho
Estratégias de cache interno a Redes Centrada em Conteúdo/ Arthur Henrique
Coutinho. – Londrina–PR, 201536 p. : il. (algumas color.) ; 30 cm.
Orientador: Prof. Dr. Bruno Bogaz Zarpelão
– Universidade Estadual de Londrina, 2015.
1. Palavra-chave1. 2. Palavra-chave2. I. Orientador. II. Universidade xxx. III.
Faculdade de xxx. IV. Título
CDU 02:141:005.7
ARTHUR HENRIQUE COUTINHO
ESTRATÉGIAS DE CACHE INTERNO A REDES
CENTRADA EM CONTEÚDO
Trabalho de Conclusão de Curso apresentado
ao curso de Bacharelado em Ciência da Computação da Universidade Estadual de Londrina para obtenção do título de Bacharel em
Ciência da Computação.
BANCA EXAMINADORA
Prof. Dr. Bruno Bogaz Zarpelão
Universidade Estadual de Londrina
Orientador
Prof. Dr. Segundo Membro da Banca
Universidade/Instituição do Segundo
Membro da Banca
Prof. Dr. Terceiro Membro da Banca
Universidade/Instituição do Terceiro
Membro da Banca
Prof. Ms. Quarto Membro da Banca
Universidade/Instituição do Quarto
Membro da Banca
Londrina–PR, 24 de novembro de 2015
AGRADECIMENTOS
Agradecimentos
COUTINHO, A. H.. Estratégias de cache interno a Redes Centrada em Conteúdo. 36 p. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) –
Universidade Estadual de Londrina, Londrina–PR, 2015.
RESUMO
Resumo
Palavras-chave: Latex. Template ABNT-DC-UEL. Editoração de texto.
COUTINHO, A. H.. Title of the Work. 36 p. Final Project (Bachelor of Science in
Computer Science) – State University of Londrina, Londrina–PR, 2015.
ABSTRACT
This is the english abstract. The Abstract in English should be faithful to the Resumo in
Portuguese, but not a literal translation.
Keywords: Latex. ABNT-DC-UEL. Text editoration.
LISTA DE ILUSTRAÇÕES
LISTA DE TABELAS
LISTA DE ABREVIATURAS E SIGLAS
RTE
Redundant Traffic Elimination
SUMÁRIO
1
INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2
WEBCACHES . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3
CACHE INTERNO À REDE BASEADO EM DEEP PACKET INSPECTION . . . . . . . . . . . . . . . . . . . . . . . . .
23
4
CONTENT DELIVERY NETWORKS . . . . . . . . . . . . . .
25
5
INFORMATION CENTRIC NETWORKS . . . . . . . . . . .
27
6
DISCUSSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
7
CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
Referências
33
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1 INTRODUÇÃO
Neste trabalho, serão relacionados (encadeados) os antigos estudos de cache em
rede (Webproxy, CDN, fingerprint), com as mais recentes propostas de funcionamento de
cache em ICNs.
Existe o problema do Tráfego Redundante. Os backbones são alvos desse problema.
Alvos do problema: - backbones - servidores; consequencias nos dois casos: - maior latência
nas comunicação; - servidores congestionados. As empresas que administram os backbones
estão preocupadas em entregar todos os pacotes que a rede demanda. Atualmente, ainda
há a Qualidade de Serviço para os backbones admins se preocuparem.
Na literatura, a palavra chave para resolver esse problema é Eliminação de Tráfego
Redundante (RTE). As propostas começaram a surgir há 20 anos (1994) com os projetos de
Webcache. Webcaches são suscetíveis a Flash Crowds (também chamado Slashdot effect),
o que limita sua escalabilidade. A cooperação entre diversos Webcaches é hierárquica e
por HTTP apenas.
Em 1999, surge o primeiro artigo propondo RTE baseada em Deep Packet Inspection (DPI). Entre 2000 e 2010 aparece um número razoável de propostas relacionadas a
DPI com Fingerprinting, inspiradas no Boom dos algoritmos de busca do Google. Esse
tipo de abordagem também é chamada Transparent Caching. Desde meados deste período,
RTE com DPI começa a se mostrar inviável: escalabilidade baixa, equipamento caro, difícil lidar com dados criptografados, cache armazena só alguns segundos ou minutos de
tráfego. Quanto aos dados criptografados, o máximo que se conseguiu foi a substituição
de trechos do pacote IP, como se fosse uma Delta Compression.
Paralelamente, há o surgimento das redes CDN, seguidas de uma grande evolução.
As CDNs tornaram-se um serviço colossal com grande retorno financeiro. Diferentes empresas desenvolvem seu próprio software e solução de CDN. Consequências: - Diferentes
redes CDN não coordenam-se. - É necessário configuração explícia dos WebApps. - É
necessário contrato específico entre provedor de conteúdo e administrador CDN. Quando
o administrador CDN é dono de um Backbone, como a Level 3, pode haver convergência
do serviço e da operação da rede (IT/Network convergence). Porém, a convergência total
é impossível.
A área de Redes de Cache foi incentivada por: - Webcaches - CDN - Investigações
de aninhamento de buffers em redes IP. Os estudos são modelagens matemáticas de topologias de redes de cache. Cada estudo propõe uma topologia otimizada para algum tipo
de conteúdo ou operação vigente na rede. Em 1997, começou-se a especular se o conteúdo
armazenado nos Webcaches seguia uma distribuição Zipf de popularidade. Foi constatado
20
que, na verdade, seguia uma distribuição Zipf-like. Essa distribuição foi muito usada na
geração de testes para os modelos propostos.
Em 2001 surge o projeto TRIAD, uma ICN. A partir de 2006, começam a ganhar
força outros projetos de ICN. Em 2009 surge o CCN e, logo em seguida, o NDN. Após
surgirem as primeiras implementações de referência do protocolo, vários estudos de viabilidade começam a ser feitos. Um desses estudos (2011) verifica se há hardware capaz de
suportar a migração de todos os endereços DNS para um único roteador CCN/NDN. Um
dos principais estudos é a boa performance do cache. Estudos de performance de cache
reaproveitam muito do conhecimento acumulado na área de Redes de Cache. Muitas abordagens para o funcionamento do cache foram feitas. Recentemente, elas foram testadas
em um survey, e constatou-se que uma das que se sobressaem em termos de desempenho
é o Cache Probabilístico (que se baseia na distribuição Zipf).
21
2 WEBCACHES
Webcaches são comumente divulgados como Proxy HTTP, um nó intermediário
da rede capaz de controlar toda a comunicação HTTP ali concentrada. A identificação do
conteúdo normalmente é ajustável por Mime type. Um exemplo é o SQUID [??]. Apesar
de um Proxy não implementar apenas a função de cache, ela mostrou-se um de seus
principais atrativos.
Os primeiros Webcaches [1] objetivavam reduzir o tráfego que saía de uma Local
Area Network (LAN). Para tanto, seu posicionamento deveria ser junto ao gateway da
rede, mantendo um cache de conteúdo HTTP. Quando houvesse uma requisição de conteúdo encontrado no cache, esta seria atendida sem nenhum encaminhamento ao servidor
web original.
Este método de RTE foi o principal utilizado na década de 90, sendo amplamente
investigado para solução de outras demandas, normalmente comerciais. Uma delas é o
alívio de carga pelo excesso de requisições a servidores. Como consequência, rapidamente
foi proposto o conceito de Webcache distribuído e de Proxy Reverso.
Webcaches distribuídos mitigam sobrecarga e congestionamento de servidores duplicando e distribuindo conteúdos frequentes entre nós de uma infraestrutura hierárquica.
Tais nós são conscientes de uma topologia semelhante a uma árvore, onde o fluxo vai se
afunilando em direção a um gateway (raiz), no caso de requisições, ou em direção à borda
(folhas), nos caso de respostas.
A distribuição mantém a média reduzida de latência entre requerinte e provedor
porém em uma escala maior, focando em todo um domínio além da LAN. A distribuição
desse conteúdo é realizada por algoritmos cujas prioridades são:
∙ Localidade de dados;
∙ Load awareness.
23
3 CACHE INTERNO À REDE BASEADO EM DEEP PACKET INSPECTION
25
4 CONTENT DELIVERY NETWORKS
27
5 INFORMATION CENTRIC NETWORKS
29
6 DISCUSSÃO
31
7 CONCLUSÃO
Sed consequat tellus et tortor. Ut tempor laoreet quam. Nullam id wisi a libero
tristique semper. Nullam nisl massa, rutrum ut, egestas semper, mollis id, leo. Nulla
ac massa eu risus blandit mattis. Mauris ut nunc. In hac habitasse platea dictumst.
Aliquam eget tortor. Quisque dapibus pede in erat. Nunc enim. In dui nulla, commodo
at, consectetuer nec, malesuada nec, elit. Aliquam ornare tellus eu urna. Sed nec metus.
Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.
Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis
egestas.
Phasellus id magna. Duis malesuada interdum arcu. Integer metus. Morbi pulvinar
pellentesque mi. Suspendisse sed est eu magna molestie egestas. Quisque mi lorem, pulvinar eget, egestas quis, luctus at, ante. Proin auctor vehicula purus. Fusce ac nisl aliquam
ante hendrerit pellentesque. Class aptent taciti sociosqu ad litora torquent per conubia
nostra, per inceptos hymenaeos. Morbi wisi. Etiam arcu mauris, facilisis sed, eleifend non,
nonummy ut, pede. Cras ut lacus tempor metus mollis placerat. Vivamus eu tortor vel
metus interdum malesuada.
Sed eleifend, eros sit amet faucibus elementum, urna sapien consectetuer mauris,
quis egestas leo justo non risus. Morbi non felis ac libero vulputate fringilla. Mauris libero
eros, lacinia non, sodales quis, dapibus porttitor, pede. Class aptent taciti sociosqu ad
litora torquent per conubia nostra, per inceptos hymenaeos. Morbi dapibus mauris condimentum nulla. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur
ridiculus mus. Etiam sit amet erat. Nulla varius. Etiam tincidunt dui vitae turpis. Donec
leo. Morbi vulputate convallis est. Integer aliquet. Pellentesque aliquet sodales urna.
33
REFERÊNCIAS
[1] GLASSMAN, S. A caching relay for the World Wide Web. Computer Networks and
ISDN Systems, v. 27, n. 2, p. 165–173, 1994. ISSN 01697552.
[2] AGGARWAL, B. et al. EndRE: an end-system redundancy elimination
service for enterprises. NSDI’10 Proceedings of the 7th USENIX conference on
Networked systems design and implementation, p. 28, 2010. Disponível em:
<http://dl.acm.org/citation.cfm?id=1855711.1855739>.
[3] ALMEIDA, F.; LOURENÇO, J. Information Centric Networks – Design Issues ,
Principles and Approaches. International Journal of Latest . . . , v. 3, n. September,
p. 58–66, 2012. Disponível em: <http://www.ojs.excelingtech.co.uk/index.php/
IJLTC/article/view/468>.
[4] ANAND, A. et al. Packet caches on routers: the implications of universal redundant
traffic elimination. Sigcomm, v. 38, p. 219–230, 2008. ISSN 01464833. Disponível
em: <http://portal.acm.org/citation.cfm?id=1402958.1402984>.
[5] ANAND, A. et al. Redundancy in network traffic: findings and implications.
Proceedings of SIGMETRICS/Performance’09, p. 37–48, 2009. Disponível em:
<http://portal.acm.org/citation.cfm?id=1555355>.
[6] ANAND, A.; SEKAR, V.; AKELLA, A. SmartRE: an architecture for
coordinated network-wide redundancy elimination. SIGCOMM Comput.
Commun. Rev., v. 39, n. 4, p. 87–98, 2009. ISSN 01464833. Disponível em:
<http://doi.acm.org/10.1145/1594977.1592580$\delimiter"026E30F$nhttp:
//dl.acm.org/ft{\_}gateway.cfm?id=1592580{&}ty>.
[7] ARAUJO, J. et al. Energy efficient content distribution. Communications (ICC),
2013 IEEE International Conference on, p. 4233–4238, 2013.
[8] ARIANFAR, S.; NIKANDER, P.; OTT, J. On content-centric router design
and implications. Proceedings of the Re-Architecting the Internet Workshop on ReARCH ’10, v. 9, p. 1, 2010. Disponível em: <http://portal.acm.org/citation.cfm?
doid=1921233.1921240>.
[9] BALL, N. A Distributed Web Cache using Load-Aware Network Coordinates. 2008.
[10] BRESLAU, L. et al. Web caching and Zipf-like distributions: evidence and
implications. Ieee Infocom, v. 1, n. c, p. 126–134, 1999. ISSN 0743-166X.
[11] CAROFIGLIO, G. et al. From content delivery today to information centric
networking. Computer Networks, Elsevier B.V., v. 57, n. 16, p. 3116–3127, 2013.
ISSN 13891286. Disponível em: <http://dx.doi.org/10.1016/j.comnet.2013.07.002>.
[12] CHAI, W. K. et al. Cache “less for more” in information-centric networks (extended
version). Computer Communications, v. 36, n. 7, p. 758–770, 2013. ISSN 01403664.
Disponível em: <http://linkinghub.elsevier.com/retrieve/pii/S014036641300025X>.
34
[13] CHE, H.; WANG, Z.; TUNG, Y. Analysis and Design of Hierarchical Web
Caching Systems. Proceedings IEEE INFOCOM 2001. Conference on Computer
Communications, v. 3, n. 1, p. 1416–1424, 2001. ISSN 0743-166X.
[14] CHE, H.; TUNG, Y.; WANG, Z. Hierarchical Web caching systems: modeling, design
and experimental results. IEEE Journal on Selected Areas in Communications, v. 20,
n. 7, p. 1305–1314, 2002. ISSN 0733-8716. Disponível em: <http://ieeexplore.ieee.org/
ielx5/49/22158/01031903.pdf?tp={&}arnumber=1031903{&}isnumber=22158$\
delimiter"026E30F$nhttp://ieeexplore.ieee.org/xpls/abs{\_}all.jsp?arnumbe>.
[15] CHO, K. et al. WAVE: Popularity-based and collaborative in-network caching for
content-oriented networks. Proceedings - IEEE INFOCOM, p. 316–321, 2012. ISSN
0743166X.
[16] CHOI, J. et al. A survey on content-oriented networking for efficient content
delivery. IEEE Communications Magazine, v. 49, n. 3, p. 121–127, 2011. ISSN
01636804.
[17] COUDERT, D. et al. Robust Redundancy Elimination for Energy-Aware
Routing. 2013 IEEE International Conference on Green Computing and
Communications and IEEE Internet of Things and IEEE Cyber, Physical
and Social Computing, n. GreenCom, p. 179–186, 2013. Disponível em:
<http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6682065>.
[18] HALEPOVIC, E.; WILLIAMSON, C.; GHADERI, M. DYNABYTE: A Dynamic
Sampling Algorithm for Redundant Content Detection. 2011 Proceedings of 20th
International Conference on Computer Communications and Networks (ICCCN),
p. 1–8, 2011. Disponível em: <http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.
htm?arnumber=6005799>.
[19] HALEPOVIC, E.; WILLIAMSON, C.; GHADERI, M. Enhancing redundant
network traffic elimination. Computer Networks, v. 56, n. 2, p. 795–809, 2012. ISSN
13891286. Disponível em: <http://dx.doi.org/10.1016/j.comnet.2011.08.020>.
[20] HARAHAP, E. et al. Distributed algorithm for router-based management of replica
server in next-CDN infrastructure. Proceedings - 2013 International Conference on
Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2013, p.
266–272, 2013.
[21] KIM, Y.; YEOM, I. Performance analysis of in-network caching for content-centric
networking. Computer Networks, Elsevier B.V., v. 57, n. 13, p. 2465–2482, 2013.
ISSN 13891286. Disponível em: <http://dx.doi.org/10.1016/j.comnet.2012.11.026>.
[22] LI, Z.; SIMON, G.; GRAVEY, A. Caching Policies for In-Network Caching.
2012 21st International Conference on Computer Communications and Networks
(ICCCN), p. 1–7, 2012. Disponível em: <http://ieeexplore.ieee.org/lpdocs/epic03/
wrapper.htm?arnumber=6289289>.
[23] LUMEZANU, C. et al. The effect of packet loss on redundancy elimination
in cellular wireless networks. Proceedings of the 10th annual conference
on Internet measurement - IMC ’10, p. 294, 2010. Disponível em: <http:
//dl.acm.org/citation.cfm?id=1879141.1879179>.
35
[24] MANUEL, C.; CABRAL, S.; ROTHENBERG, C. E. Mini-CCNx : Uma plataforma
de prototipagem rápida para Redes Orientadas a Conteúdo. 2013.
[25] PERINO, D. et al. A Reality Check for Content Centric Networking. Acm Icn
2011, p. 44–49, 2011. Disponível em: <http://diegoperino.com/publications/
icn06c-perino.pdf>.
[26] POLTEROCK, J. et al. The First Named Data Networking Community Meeting (
NDNcomm ) Categories and Subject Descriptors. 2015.
[27] REZAZAD, M.; TAY, Y. C. ndn||mem - an Architecture to Alleviate the Memory
Bottleneck for Named Data Networking. Proceedings of the 2013 workshop on
Student workhop - CoNEXT Student Workhop ’13, p. 1–4, 2013. Disponível em:
<http://dl.acm.org/citation.cfm?doid=2537148.2537154>.
[28] ROSENSWEIG, E. J.; KUROSE, J. Breadcrumbs: Efficient, best-effort content
location in cache networks. Ieee Infocom, p. 2631–2635, 2009. ISSN 0743166X.
[29] ROSENSWEIG, E. J.; KUROSE, J.; TOWSLEY, D. Approximate Models for
General Cache Networks. 2010 Proceedings IEEE INFOCOM, p. 1–9, 2010. ISSN
0743-166X. Disponível em: <http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?
arnumber=5461936>.
[30] ROSSINI, G.; ROSSI, D. Evaluating CCN multi-path interest forwarding strategies.
Computer Communications, Elsevier B.V., v. 36, n. 7, p. 771–778, 2013. ISSN
01403664. Disponível em: <http://dx.doi.org/10.1016/j.comcom.2013.01.008>.
[31] SANADHYA, S. et al. Asymmetric Caching: Improved Network Deduplication
for Mobile Devices. Proceedings of the 18th annual international conference
on Mobile computing and networking - Mobicom ’12, p. 161, 2012. Disponível
em: <http://dl.acm.org/citation.cfm?id=2348565$\delimiter"026E30F$nhttp:
//dl.acm.org/citation.cfm?doid=2348543.2348565>.
[32] SHI, L. et al. An Applicative Study of Zipf ’ s Law on Web Cache. v. 12, n. 4, p.
49–58, 2006.
[33] SPRING, N. T.; WETHERALL, D. A protocol-independent technique for
eliminating redundant network traffic. Sigcomm, v. 30, n. 4, p. 87–95, 2000. ISSN
01464833.
[34] SREBRNY, P. et al. CacheCast: Eliminating Redundant Link Traffic for
Single Source Multiple Destination Transfers. 2010 IEEE 30th International
Conference on Distributed Computing Systems, p. 209–220, 2010. Disponível em:
<http://ieeexplore.ieee.org/xpl/freeabs{\_}all.jsp?arnumber=5541>.
[35] WANG, J. M.; ZHANG, J.; BENSAOU, B. Intra-AS cooperative caching for
content-centric networks. ACM SIGCOMM Workshop of Information-centric
networking (ICN), p. 61, 2013. Disponível em: <http://dl.acm.org/citation.cfm?
doid=2491224.2491234>.
[36] WANG, J. A survey of web caching schemes for the Internet. ACM SIGCOMM
Computer Communication Review, v. 29, n. 5, p. 36, 1999. ISSN 01464833.
Disponível em: <http://dl.acm.org/citation.cfm?id=505696.505701>.
36
[37] WANG, L.; BAYHAN, S.; KANGASHARJU, J. Optimal chunking and
partial caching in information-centric networks. Computer Communications,
Elsevier B.V., v. 61, p. 48–57, 2015. ISSN 01403664. Disponível em: <http:
//www.sciencedirect.com/science/article/pii/S0140366414003740>.
[38] WONG, W.; WANG, L.; KANGASHARJU, J. Neighborhood search and admission
control in cooperative caching networks. Global Communications Conference
(GLOBECOM), 2012 IEEE, p. 2852–2858, 2012.
[39] WONG, W. et al. Content Routers: Fetching Data on Network Path. 2011 IEEE
International Conference on Communications (ICC), p. 1–6, 2011. ISSN 1550-3607.
Disponível em: <http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=
5963111>.
[40] WOO, S. et al. Comparison of Caching Strategies in Modern Cellular
Backhaul Networks. Proc. of MobiSys, p. 319, 2013. Disponível em: <http:
//dl.acm.org/citation.cfm?doid=2462456.2464442>.
[41] WU, H. et al. A novel caching scheme for the backbone of Named data networking.
IEEE International Conference on Communications, p. 3634–3638, 2013. ISSN
15503607.
[42] XU, Y.; LIU, Y.; LIU, Y. Algorithm for redundancy elimination in network traffic.
2012 2nd International Conference on Consumer Electronics, Communications and
Networks, CECNet 2012 - Proceedings, v. 3, p. 1613–1617, 2012.
[43] XU, Y. et al. A novel cache size optimization scheme based on manifold
learning in Content Centric Networking. Journal of Network and Computer
Applications, Elsevier, v. 37, n. 1, p. 273–281, 2014. ISSN 10848045. Disponível em:
<http://dx.doi.org/10.1016/j.jnca.2013.03.002>.
[44] XYLOMENOS, G. et al. A Survey of Information-Centric Networking Research.
IEEE Communications Surveys & Tutorials, v. 16, n. 2, p. 1024–1049, 2014. ISSN
1553-877X. Disponível em: <http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?
arnumber=6563278>.
[45] ZARPELAO, B. B. et al. Detecção de Anomalias em Redes de Computadores.
Network, 2009.
[46] ZHANG, G.; LI, Y.; LIN, T. Caching in information centric networking: A survey.
Computer Networks, Elsevier B.V., v. 57, n. 16, p. 3128–3141, 2013. ISSN 13891286.
Disponível em: <http://dx.doi.org/10.1016/j.comnet.2013.07.007>.
[47] ZHANG, M.; LUO, H.; ZHANG, H. A Survey of Caching Mechanisms in
Information-Centric Networking. IEEE Communications Surveys & Tutorials, v. 17,
n. 3, p. 1–1, 2015. ISSN 1553-877X. Disponível em: <http://ieeexplore.ieee.org/
lpdocs/epic03/wrapper.htm?arnumber=7080842>.